Graphs

Shortest Path Algorithms

Pre-Requisite: Depth-First Search, Breadth-First Search
Finding shortest paths is one of the most fundamental graph problems. The algorithm you choose depends on one thing: what are the edge weights?
Shortest path algorithm decision tree
Let's have a look on each algorithm below.

1. BFS: When All Edges Are Equal

If every edge has the same cost (or weight = 1), BFS is your shortest path algorithm. If you're unfamiliar with BFS, start with our BFS introduction.

How BFS Finds Shortest Paths

BFS explores nodes level by level using a queue. The first time you reach a node, you've found the shortest path to it and no other path can be shorter because all edges cost the same.
1. Initializedist[start] = 0queue = [start]2. Dequeuenode = queue.pop()explore neighbors3. Updateif neighbor unvisited:dist[neighbor] = dist[node] + 1queue.add(neighbor)repeat until queue empty
Why does this work? The queue processes nodes in order of discovery. Nodes discovered first (closer to source) get processed before nodes discovered later (farther from source). This layer-by-layer exploration guarantees shortest paths.

Walkthrough

Let's trace through BFS on this graph in the visual below, starting from node 0:
  1. Initialize: Set dist[0] = 0 and add 0 to the queue
  2. Process 0: Discover neighbors 1 and 2 → set dist[1] = 1, dist[2] = 1, add both to queue
  3. Process 1: Discover neighbor 3 → set dist[3] = 2
  4. Process 2: Neighbors 3 and 4 → 3 already visited, set dist[4] = 2
  5. Continue until queue empty
Notice how BFS finds all nodes at distance 1 before any node at distance 2. This layer-by-layer exploration is what guarantees shortest paths.
Visualization
001∞2∞3∞4∞5∞

Initialize: set dist[0] = 0, enqueue 0

0 / 12

Click Show Code in the visualization above to see the whole implementation.

Complexity

Time: O(V + E) as each node is dequeued once, and each edge is examined once when we check neighbors.
Space: O(V) as the queue can hold at most V nodes, and we store distances for V nodes.

When to Use BFS

  • Grid navigation (moving up/down/left/right)
  • Unweighted graph traversal
  • Finding minimum number of steps/moves

Problems That Use BFS for Shortest Path

If a problem asks for "minimum moves" or "shortest path" in a grid or unweighted graph, try BFS first. It's simpler and often sufficient.

2. Dijkstra's Algorithm: Weighted Edges

Dijkstra's is the most important shortest path algorithm for interviews. It handles graphs where edges have different positive weights.
The idea is to always explore the cheapest unexplored node. We can use a min-heap (priority queue) to efficiently find it.

How Dijkstra Works

1. Initializedist[source] = 0dist[others] = ∞heap = [(0, source)]2. Pop minimum(d, node) = heap.pop()if d > dist[node]: skip(stale entry)3. Relaxfor each neighbor:new = d + weightif new < dist: updaterepeat until heap empty4. Return resultdist[] now contains shortest paths from source
The key insight is relaxation: for each edge, we ask "can we reach this neighbor faster by going through the current node?" If yes, we update the distance and add the neighbor to the heap.

Walkthrough

Let's trace Dijkstra on this weighted graph below, starting from node 0. The edges are: 0→1 (weight 4), 0→2 (weight 1), 2→1 (weight 2), 2→3 (weight 5), 1→3 (weight 1), 3→4 (weight 3).
  1. Initialize: dist[0] = 0, all others = ∞. Heap = [(0, 0)]
  2. Pop (0, 0): Process node 0. Check edges:
    • 0→1: dist[1] = 0 + 4 = 4. Add (4, 1) to heap.
    • 0→2: dist[2] = 0 + 1 = 1. Add (1, 2) to heap.
  3. Pop (1, 2): Process node 2 (smallest distance!). Check edges:
    • 2→1: 0 + 1 + 2 = 3 < 4. Update dist[1] = 3. Add (3, 1) to heap.
    • 2→3: dist[3] = 1 + 5 = 6. Add (6, 3) to heap.
  4. Pop (3, 1): Process node 1. Check edges:
    • 1→3: 3 + 1 = 4 < 6. Update dist[3] = 4. Add (4, 3) to heap.
  5. Pop (4, 3): Process node 3. dist[4] = 4 + 3 = 7.
  6. Continue until heap empty.
Notice how we found a shorter path to node 1: the direct path 0→1 costs 4, but going 0→2→1 costs only 3. Dijkstra discovered this by always processing the cheapest node first.
Visualization
411253001∞2∞3∞4∞Min-Heap: [(0,0)]

Initialize: set dist[0] = 0, push (0, 0) to min-heap

0 / 18

Why It Works

Dijkstra is greedy: it always processes the node with the smallest known distance. Because all edge weights are non-negative, once we've processed a node, we've found its shortest path. No later discovery can improve it as for any other path would have to go through a node with equal or greater distance, then add more non-negative weight.
Dijkstra fails with negative edge weights. If an edge can reduce the total cost, the greedy assumption breaks down and we might find a shorter path after we've already "finalized" a node.

Complexity

Time: O((V + E) log V) with a binary heap
  • Each node is added to the heap at most once: O(V log V)
  • Each edge might trigger a heap update: O(E log V)
Space: O(V) for the distances map and heap

When to Use Dijkstra

  • Weighted graphs with non-negative edges
  • Finding shortest path from one source to all nodes
  • Problems involving "minimum cost" or "minimum time"

Classic Dijkstra Problems

3. Bellman-Ford: When Negative Weights Exist

Bellman-Ford handles graphs with negative edge weights and can detect negative cycles.

How Bellman-Ford Works

The algorithm repeatedly relaxes every edge: for each edge, check "if we can reach the destination faster by going through this edge?" If yes, update the distance. Repeat this for all edges, V-1 times.
1. Initializedist[source] = 0dist[others] = ∞2. Relax all edgesfor each edge (u, v, w):if dist[u] + w < dist[v]: updaterepeat V-1 times3. Check cyclesrelax once moreany change = cycle

Why V-1 Iterations?

The longest possible shortest path visits every node exactly once, which means it has at most V-1 edges. Each iteration of Bellman-Ford can discover shortest paths that are one edge longer than before. So after V-1 iterations, we've found every possible shortest path.

Walkthrough

Let's trace Bellman-Ford on the below given graph with edges: 0→1 (weight 5), 1→2 (weight -2), 2→3 (weight 1), 3→4 (weight 1). Starting from node 0.
The negative edge 1→2 is why Dijkstra fails here. Dijkstra would process node 2 (if reachable via some other path) before discovering that going 0→1→2 is actually cheaper due to the -2 edge.
  1. Initialize: dist[0] = 0, all others = ∞
  2. Iteration 1: Relax all edges
    • Edge 0→1: dist[1] = 0 + 5 = 5
    • Edges 1→2, 2→3, 3→4: can't relax (source dist = ∞)
  3. Iteration 2: Relax all edges again
    • Edge 1→2: dist[2] = 5 + (-2) = 3
  4. Iteration 3: dist[3] = 3 + 1 = 4
  5. Iteration 4: dist[4] = 4 + 1 = 5
Each iteration propagates the shortest path one edge further. This is slower than Dijkstra, but it handles negative weights correctly.
Visualization
5-211001∞2∞3∞4∞

Initialize: dist[0] = 0, all other distances = ∞. Will run V-1 = 4 iterations.

0 / 26

Complexity

Time: O(V · E) as it is much slower than Dijkstra for large graphs, but handles negative weights
Space: O(V) for the distances array

When to Use Bellman-Ford

  • Graph has negative edge weights
  • Need to detect negative cycles
  • Problems involving arbitrage or exchange rates
In interviews, Bellman-Ford is more commonly discussed than implemented. Know why Dijkstra fails with negative weights and how Bellman-Ford fixes it.

4. Floyd-Warshall: All Pairs Shortest Path

What if you need the shortest path between every pair of nodes? Running Dijkstra V times on each node works, but Floyd-Warshall is a simpler solution for dense graphs or small V.

How Floyd-Warshall Works

We can solve this with dynamic programming. The idea is for each node k, check if using k as an intermediate improves the path from i to j.
1. Initializedist[i][i] = 0dist[i][j] = edge weight or ∞2. Try each intermediate kfor all pairs (i, j):dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])for k = 0 to V-1Done!dist[i][j] =shortest i→j
The DP recurrence: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After considering node k as an intermediate, dist[i][j] holds the shortest path using only nodes 0 through k.

Walkthrough

Let's trace Floyd-Warshall on a 4-node graph with edges: 0→1 (3), 0→2 (8), 1→2 (2), 1→3 (7), 2→3 (1).
  1. Initialize: Fill matrix with edge weights, ∞ for no edge, 0 on diagonal
  2. k=0: Try node 0 as intermediate. For example, is 1→0→2 shorter than 1→2? No, because there's no edge 1→0.
  3. k=1: Try node 1 as intermediate. Is 0→1→2 shorter than 0→2? Yes! 3+2=5 < 8. Update dist[0][2] = 5.
  4. k=2: Try node 2 as intermediate. Is 0→2→3 shorter than 0→3? Yes! 5+1=6 < ∞. Also 1→2→3 = 2+1=3 < 7.
  5. k=3: Try node 3. No improvements found.
The matrix now contains shortest paths between all pairs.
Visualization
38217012301230∞∞∞∞1∞∞∞∞2∞∞∞∞3∞∞∞∞

Initialize distance matrix: set dist[i][j] = edge weight if edge exists, ∞ otherwise, dist[i][i] = 0

0 / 10

Complexity

Time: O(V³) because of three nested loops over all vertices
Space: O(V²) because of the distance matrix

When to Use Floyd-Warshall

  • Need distances between all pairs
  • Small number of nodes (V ≤ 400 or so)
  • Dense graphs where E ≈ V²

Classic Floyd-Warshall Problem

Quick Reference

Here's your cheat sheet for interviews:

Algorithm Selection

SituationUse This
All edges weight 1BFS
Different positive weightsDijkstra
Negative weights possibleBellman-Ford
Need all pairsFloyd-Warshall
Weights are 0 or 1 only0-1 BFS (optimization)

Complexity Comparison

AlgorithmTimeSpace
BFSO(V + E)O(V)
DijkstraO((V + E) log V)O(V)
Bellman-FordO(V · E)O(V)
Floyd-WarshallO(V³)O(V²)

Key Takeaways

  1. BFS handles unweighted graphs: It's simpler than you think. Many "shortest path" problems are just BFS.
  2. Dijkstra is your default for weighted graphs: Learn and practice it. It appears in ~70% of weighted shortest path interview problems.
  3. Know when algorithms fail: Dijkstra fails with negative weights. BFS fails with varying weights. Understanding why is more valuable than memorizing implementations.
  4. State modification is common: Real interview problems often add constraints that require tracking extra state beyond just the current node.

Practice Problems

Ready to apply these concepts? Work through these problems:

Mark as read

Next: Network Delay Time

© 2026 Optick Labs Inc. All rights reserved.