Shortest Path Algorithms
The problem: Given a graph (nodes connected by edges), find the path from a source node to a destination with the minimum total cost (distance, time, weight).
Why this matters in interviews: ~15% of graph problems are shortest-path variants. Once you recognize the type, you pick the right algorithm and the code is mostly template.
When to Use Which (Decision Tree)
flowchart TD
START["Need shortest path?"]:::client
W{"Are edges weighted?"}:::service
UW["BFS<br/>O(V+E)"]:::data
ZO{"Weights only 0 or 1?"}:::service
ZOB["0-1 BFS (Deque)<br/>O(V+E)"]:::data
NEG{"Any negative edges?"}:::service
DIJ["Dijkstra<br/>O((V+E) log V)"]:::data
DAG{"Is it a DAG?"}:::service
TOPO["Topo Sort + Relax<br/>O(V+E)"]:::data
BF["Bellman-Ford<br/>O(VE)"]:::data
ALL{"Need ALL pairs?"}:::service
FW["Floyd-Warshall<br/>O(V³)"]:::data
START --> W
W -->|"No (all equal)"| UW
W -->|"Yes"| ZO
ZO -->|"Yes"| ZOB
ZO -->|"No"| NEG
NEG -->|"No"| DIJ
NEG -->|"Yes"| DAG
DAG -->|"Yes"| TOPO
DAG -->|"No (has cycles)"| BF
START -->|"All pairs?"| ALL
ALL --> FW
classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
Rule of thumb: Start with BFS (unweighted) or Dijkstra (weighted). Only reach for Bellman-Ford when you see negative edges or “at most K stops.”
1. BFS (Breadth-First Search) — Unweighted Graphs
When: All edges have equal weight (or no weight). Every step costs 1.
Intuition: Imagine dropping a stone in a pond. Ripples spread outward one layer at a time. BFS explores all nodes 1 step away, then 2 steps, then 3 — so the first time you reach a node is guaranteed to be the shortest path.
How it works (step by step):
flowchart LR
A["A (start)<br/>dist=0"]:::client
B["B<br/>dist=1"]:::service
C["C<br/>dist=1"]:::service
D["D<br/>dist=2"]:::data
E["E (end)<br/>dist=2"]:::data
A --> B
A --> C
B --> D
C --> E
B --> E
classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
- Start at A (distance = 0). Add A to a queue.
- Process A: discover B and C (distance = 1). Add both to queue.
- Process B: discover D and E (distance = 2). Add to queue.
- Process C: discover E — but E is already visited (distance = 2). Skip.
- We reach E with distance 2. That’s the shortest path.
Key insight: The queue ensures we always process nodes in order of their distance from the source. First arrival = shortest path.
Complexity: O(V + E) time, O(V) space.
Code
from collections import deque
def bfs_shortest(graph, src, dst):
# graph = adjacency list: {node: [neighbors]}
queue = deque([(src, 0)]) # (node, distance)
visited = {src}
while queue:
node, dist = queue.popleft()
if node == dst:
return dist
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1 # unreachableint bfsShort(List<List<Integer>> graph, int src, int dst) {
Queue<int[]> q = new LinkedList<>();
boolean[] vis = new boolean[graph.size()];
q.offer(new int[]{src, 0});
vis[src] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == dst) return cur[1];
for (int nb : graph.get(cur[0])) {
if (!vis[nb]) {
vis[nb] = true;
q.offer(new int[]{nb, cur[1] + 1});
}
}
}
return -1;
}int bfsShort(vector<vector<int>>& graph, int src, int dst) {
queue<pair<int,int>> q;
vector<bool> vis(graph.size(), false);
q.push({src, 0});
vis[src] = true;
while (!q.empty()) {
auto [node, dist] = q.front(); q.pop();
if (node == dst) return dist;
for (int nb : graph[node]) {
if (!vis[nb]) {
vis[nb] = true;
q.push({nb, dist + 1});
}
}
}
return -1;
}function bfsShort(graph, src, dst) {
const queue = [[src, 0]];
const visited = new Set([src]);
let i = 0;
while (i < queue.length) {
const [node, dist] = queue[i++];
if (node === dst) return dist;
for (const nb of graph[node]) {
if (!visited.has(nb)) {
visited.add(nb);
queue.push([nb, dist + 1]);
}
}
}
return -1;
}Common interview problems using BFS shortest path:
- Word Ladder — each word is a node, edges connect words differing by 1 letter
- Rotting Oranges — multi-source BFS on a grid
- Shortest Path in Binary Matrix — grid BFS with 8 directions
2. Dijkstra’s Algorithm — Weighted Graphs (No Negative Edges)
When: Edges have different positive weights (road lengths, travel times). You want the cheapest path from source to all nodes.
Intuition: Like BFS, but instead of a regular queue (FIFO), we use a priority queue (min-heap) that always processes the node with the smallest known distance first. This guarantees that when we pop a node, its distance is final.
How it works (step by step):
flowchart LR
A["A (start)<br/>dist=0"]:::client
B["B<br/>dist=2"]:::service
C["C<br/>dist=4"]:::service
D["D<br/>dist=5"]:::data
E["E (end)<br/>dist=6"]:::data
A -->|"2"| B
A -->|"4"| C
B -->|"3"| D
B -->|"7"| E
C -->|"1"| D
D -->|"1"| E
classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
Walkthrough:
- Start: dist[A]=0, everything else = infinity. Heap: [(0, A)]
- Pop A (dist=0). Relax neighbors: dist[B]=2, dist[C]=4. Heap: [(2,B), (4,C)]
- Pop B (dist=2). Relax: dist[D]=min(inf, 2+3)=5, dist[E]=min(inf, 2+7)=9. Heap: [(4,C), (5,D), (9,E)]
- Pop C (dist=4). Relax: dist[D]=min(5, 4+1)=5 (no change). Heap: [(5,D), (9,E)]
- Pop D (dist=5). Relax: dist[E]=min(9, 5+1)=6. Heap: [(6,E), (9,E)]
- Pop E (dist=6). Done! Shortest path A→B→D→E costs 6.
Key insight: Once a node is popped from the heap, its distance is finalized — you’ll never find a shorter path to it. This is why negative edges break Dijkstra (a later discovery could be shorter via a negative edge, but you already finalized the node).
Complexity: O((V + E) log V) with a binary heap.
Code
import heapq
def dijkstra(graph, src, dst):
# graph = {node: [(neighbor, weight), ...]}
dist = {src: 0}
heap = [(0, src)] # (distance, node)
while heap:
d, node = heapq.heappop(heap)
if node == dst:
return d
if d > dist.get(node, float('inf')):
continue # stale entry, skip
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist.get(neighbor, float('inf')):
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return -1 # unreachableint dijkstra(List<List<int[]>> graph, int src, int dst) {
int n = graph.size();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// min-heap: [distance, node]
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] - b[0]);
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], node = cur[1];
if (node == dst) return d;
if (d > dist[node]) continue;
for (int[] edge : graph.get(node)) {
int nb = edge[0], w = edge[1];
if (d + w < dist[nb]) {
dist[nb] = d + w;
pq.offer(new int[]{dist[nb], nb});
}
}
}
return -1;
}int dijkstra(vector<vector<pair<int,int>>>& graph, int src, int dst) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
dist[src] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [d, node] = pq.top(); pq.pop();
if (node == dst) return d;
if (d > dist[node]) continue;
for (auto [nb, w] : graph[node]) {
if (d + w < dist[nb]) {
dist[nb] = d + w;
pq.push({dist[nb], nb});
}
}
}
return -1;
}function dijkstra(graph, src, dst) {
// graph = [[{to, w}, ...], ...] (adjacency list)
const n = graph.length;
const dist = Array(n).fill(Infinity);
dist[src] = 0;
// Simple heap using sorted insertion (for interview; use a real heap lib in prod)
const heap = [[0, src]]; // [dist, node]
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]);
const [d, node] = heap.shift();
if (node === dst) return d;
if (d > dist[node]) continue;
for (const {to, w} of graph[node]) {
if (d + w < dist[to]) {
dist[to] = d + w;
heap.push([dist[to], to]);
}
}
}
return -1;
}Common interview problems using Dijkstra:
- Network Delay Time — classic single-source shortest path
- Path With Minimum Effort — Dijkstra on a grid where edge weight = absolute height difference (complex grid I/O — practice on LeetCode directly)
3. Bellman-Ford — When Edges Can Be Negative
When: Graph has negative edge weights, OR you need “shortest path with at most K edges” (the classic “cheapest flights within K stops” variant).
Intuition: Relax every edge, V-1 times. Each round guarantees we’ve found the shortest path using at most that many edges. Brute-force but handles negative weights correctly.
How it works:
flowchart LR
A["A<br/>dist=0"]:::client
B["B<br/>dist=1"]:::service
C["C<br/>dist=3"]:::service
D["D<br/>dist=2"]:::data
A -->|"1"| B
A -->|"4"| C
B -->|"-1"| C
B -->|"2"| D
C -->|"-1"| D
classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
Round 1: Relax all edges. dist[B]=1, dist[C]=4, dist[D]=3. Round 2: Relax again. dist[C]=min(4, 1+(-1))=0. But wait — dist[C] via B is 1+(-1)=0… actually let me recompute. A→B=1, B→C: 1+(-1)=0, C→D: 0+(-1)=-1. After 2 rounds, dist[D]=min(3, -1)=…
Actually let me give a cleaner example:
The algorithm:
- Initialize dist[src] = 0, all others = infinity
- Repeat V-1 times: for every edge (u, v, weight), if dist[u] + weight < dist[v], update dist[v]
- After V-1 rounds, all shortest paths are found
- (Optional) Do one more round — if any distance decreases, there’s a negative cycle
Why V-1 rounds? The longest shortest path has at most V-1 edges. Each round “extends” paths by one edge. So after V-1 rounds, even the longest path is optimal.
The K-stops interview trick: If the problem says “at most K stops” (like cheapest flights), just run K rounds instead of V-1. After K rounds, you have the shortest path using at most K edges.
Complexity: O(V × E) time, O(V) space. Slower than Dijkstra, but handles negatives.
Code
def bellman_ford(n, edges, src, dst):
# edges = [(u, v, weight), ...]
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1): # V-1 rounds
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative cycle (optional)
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return -1 # negative cycle exists
return dist[dst] if dist[dst] != float('inf') else -1int bellmanFord(int n, int[][] edges, int src, int dst) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i < n - 1; i++) {
for (int[] e : edges) {
if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
dist[e[1]] = dist[e[0]] + e[2];
}
}
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}int bellmanFord(int n, vector<array<int,3>>& edges, int src, int dst) {
vector<int> dist(n, INT_MAX);
dist[src] = 0;
for (int i = 0; i < n - 1; i++) {
for (auto& [u, v, w] : edges) {
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}function bellmanFord(n, edges, src, dst) {
const dist = Array(n).fill(Infinity);
dist[src] = 0;
for (let i = 0; i < n - 1; i++) {
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
return dist[dst] === Infinity ? -1 : dist[dst];
}Common interview problems using Bellman-Ford:
- Cheapest Flights Within K Stops — run K+1 rounds instead of V-1 (complex multi-param I/O — practice on LeetCode directly)
- Negative cycle detection — if V-th round still reduces distances
4. 0-1 BFS — When Weights Are Only 0 or 1
When: Edge weights are only 0 or 1. Common in grid problems where some moves are “free” (e.g., walking on a road = 0, breaking a wall = 1).
Intuition: Like BFS, but use a deque (double-ended queue) instead of a regular queue. Weight-0 edges go to the front (process next, same distance), weight-1 edges go to the back (process later, distance + 1). This keeps the deque sorted by distance without needing a heap — O(V+E) instead of O((V+E) log V).
How it works:
flowchart LR
A["A<br/>dist=0"]:::client
B["B<br/>dist=0 (free edge)"]:::client
C["C<br/>dist=1"]:::service
D["D<br/>dist=1"]:::service
A -->|"0"| B
A -->|"1"| C
B -->|"1"| D
C -->|"0"| D
classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
- A→B costs 0: push B to front of deque (same distance layer)
- A→C costs 1: push C to back of deque (next distance layer)
Complexity: O(V + E) — same as BFS! Much faster than Dijkstra for 0-1 graphs.
Code
from collections import deque
def bfs01(graph, src, dst):
# graph = {node: [(neighbor, weight)]} where weight is 0 or 1
dist = {src: 0}
dq = deque([src])
while dq:
node = dq.popleft()
if node == dst:
return dist[node]
for neighbor, w in graph[node]:
new_dist = dist[node] + w
if new_dist < dist.get(neighbor, float('inf')):
dist[neighbor] = new_dist
if w == 0:
dq.appendleft(neighbor) # front — same layer
else:
dq.append(neighbor) # back — next layer
return -1int bfs01(List<List<int[]>> graph, int src, int dst) {
int n = graph.size();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
Deque<Integer> dq = new ArrayDeque<>();
dq.offerFirst(src);
while (!dq.isEmpty()) {
int node = dq.pollFirst();
if (node == dst) return dist[node];
for (int[] edge : graph.get(node)) {
int nb = edge[0], w = edge[1];
if (dist[node] + w < dist[nb]) {
dist[nb] = dist[node] + w;
if (w == 0) dq.offerFirst(nb);
else dq.offerLast(nb);
}
}
}
return -1;
}int bfs01(vector<vector<pair<int,int>>>& graph, int src, int dst) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
dist[src] = 0;
deque<int> dq;
dq.push_front(src);
while (!dq.empty()) {
int node = dq.front(); dq.pop_front();
if (node == dst) return dist[node];
for (auto [nb, w] : graph[node]) {
if (dist[node] + w < dist[nb]) {
dist[nb] = dist[node] + w;
if (w == 0) dq.push_front(nb);
else dq.push_back(nb);
}
}
}
return -1;
}function bfs01(graph, src, dst) {
const n = graph.length;
const dist = Array(n).fill(Infinity);
dist[src] = 0;
const dq = [src]; // use as deque (shift/unshift for front, push for back)
while (dq.length) {
const node = dq.shift();
if (node === dst) return dist[node];
for (const [nb, w] of graph[node]) {
if (dist[node] + w < dist[nb]) {
dist[nb] = dist[node] + w;
if (w === 0) dq.unshift(nb);
else dq.push(nb);
}
}
}
return -1;
}When to spot it: grid problems where “some cells are free to cross, some cost 1.” Classic: minimum obstacle removals to reach the corner.
5. Floyd-Warshall — All Pairs Shortest Path
When: You need the shortest distance between every pair of nodes, and the graph is small (V ≤ 400). Also handles negative edges (but no negative cycles).
Intuition: For every pair (i, j), ask: “is it shorter to go directly, or through some intermediate node k?” Try every possible intermediate k. Three nested loops — that’s the whole algorithm.
The core idea in one line:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
“Can I get from i to j cheaper by routing through k?”
Complexity: O(V³) time, O(V²) space. Only practical for V ≤ ~400.
Code
def floyd_warshall(n, edges):
# Returns dist[i][j] = shortest path from i to j
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w)
for k in range(n): # intermediate node
for i in range(n): # source
for j in range(n): # destination
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distint[][] floydWarshall(int n, int[][] edges) {
int INF = (int) 1e9;
int[][] dist = new int[n][n];
for (int[] row : dist) Arrays.fill(row, INF);
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (int[] e : edges) dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
return dist;
}vector<vector<int>> floydWarshall(int n, vector<array<int,3>>& edges) {
const int INF = 1e9;
vector<vector<int>> dist(n, vector<int>(n, INF));
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (auto& [u, v, w] : edges) dist[u][v] = min(dist[u][v], w);
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
return dist;
}function floydWarshall(n, edges) {
const INF = Infinity;
const dist = Array.from({length: n}, () => Array(n).fill(INF));
for (let i = 0; i < n; i++) dist[i][i] = 0;
for (const [u, v, w] of edges) dist[u][v] = Math.min(dist[u][v], w);
for (let k = 0; k < n; k++)
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
return dist;
}Common interview problems:
- Find the city with the smallest number of neighbors at a threshold distance
- Shortest path between all pairs in a small graph
Comparison Cheat Sheet
| Algorithm | Time | Negative edges | All pairs | Best for |
|---|---|---|---|---|
| BFS | O(V+E) | ❌ | ❌ | Unweighted (grids, word problems) |
| Dijkstra | O((V+E) log V) | ❌ | ❌ | Weighted, non-negative (most real problems) |
| Bellman-Ford | O(VE) | ✅ | ❌ | Negative edges, K-stops constraint |
| 0-1 BFS | O(V+E) | ❌ | ❌ | Weights are only 0 or 1 (obstacle grids) |
| Floyd-Warshall | O(V³) | ✅ | ✅ | All-pairs, small V (≤400) |
| Topo Sort + Relax | O(V+E) | ✅ | ❌ | DAGs only (fastest possible) |
Common Mistakes in Interviews
- Using Dijkstra with negative edges — it gives wrong answers. If you see negative weights, switch to Bellman-Ford.
- Not marking visited in BFS — leads to infinite loops and TLE.
- Processing stale heap entries in Dijkstra — always check
if d > dist[node]: continueafter popping. - Forgetting that Floyd-Warshall needs
kas the outermost loop — if you putkinside, it breaks the DP correctness. - Confusing “K stops” with “K edges” — K stops = K+1 edges. Bellman-Ford with K rounds gives paths with at most K edges (= K-1 stops).
When to Use What — Quick Reference
- Grid, all moves cost 1 → BFS
- Grid, some moves free (cost 0), some cost 1 → 0-1 BFS
- Weighted road network, find cheapest route → Dijkstra
- “Cheapest flight with at most K stops” → Bellman-Ford (K rounds)
- “Distance from every node to every other node” → Floyd-Warshall (if V ≤ 400) or run Dijkstra V times (if sparse)
- DAG (no cycles) with weights → Topological sort then relax in order (fastest: O(V+E))