Graphs
Shortest Path Algorithms
Find the minimum-cost route between vertices. Unweighted → BFS in O(V+E). Non-negative weights → Dijkstra in O((V+E) log V). Negative edges → Bellman-Ford in O(VE). Three algorithms, three constraints, one goal.
Foundations · Array · HashMap · Heap · Graph · BFS · DFS · Topo Sort · Shortest Path · Sorting · Dynamic Prog.
01
Section One · Foundation
What is Shortest Path?
The shortest path problem asks: what is the minimum total edge weight from a source vertex to a destination (or to all other vertices)? The answer depends on the type of graph. Unweighted graphs: every edge has weight 1, so BFS finds the shortest path in O(V+E) — the first time BFS reaches a vertex is the shortest distance. Weighted graphs with non-negative edges: Dijkstra's algorithm uses a priority queue to greedily process the closest unvisited vertex, running in O((V+E) log V) with a binary heap. Weighted graphs with negative edges: Bellman-Ford relaxes all edges V-1 times in O(VE), handling negative weights and detecting negative cycles. A fourth option — Floyd-Warshall — finds shortest paths between ALL pairs in O(V³), useful for dense graphs and small V. In interviews, Dijkstra dominates. BFS is the foundation (covered in its own page), and Bellman-Ford appears in problems with negative weights or "at most K stops."
Analogy: GPS navigation. You want the fastest route from home to the airport. Each road has a travel time (weight). Dijkstra is the GPS: it explores the nearest intersection first, expands outward, and guarantees the first time it reaches the airport is via the fastest route. If some roads have "negative time" (impossible in real life, but useful in problems), Bellman-Ford handles it by checking all roads multiple times.
02
Section Two · Mental Model
How It Thinks
All edge weights are 1 (or equal)
▶
Use BFS — the first visit to each vertex is the shortest path. No priority queue needed. O(V+E).
Edge weights are non-negative but vary
▶
Dijkstra: always process the vertex with the smallest tentative distance (greedy). Once a vertex is finalised, its distance is optimal. PriorityQueue gives O((V+E) log V).
Some edges have negative weights
▶
Dijkstra fails — a "cheaper" path via a negative edge could appear later. Bellman-Ford relaxes ALL edges V-1 times to catch these. O(VE).
"Relax" an edge u→v with weight w: if dist[u] + w < dist[v], update dist[v]
▶
Relaxation is the core operation of ALL shortest path algorithms. It says: "I found a shorter path to v — going through u and then taking edge u→v."
A negative cycle exists (total cycle weight < 0)
▶
Shortest path is undefined — you can keep looping to get −∞. Bellman-Ford detects this: if any edge can still be relaxed after V-1 passes → negative cycle.
Need shortest path between ALL pairs of vertices
▶
Floyd-Warshall: 3 nested loops, O(V³). Or run Dijkstra from each vertex: O(V(V+E) log V). Floyd is simpler for small, dense graphs.
03
Section Three · Unweighted
BFS — Unweighted Shortest Path
When all edges have weight 1, BFS finds the shortest path naturally — the first time it reaches a vertex is the minimum number of edges from the source. This is the simplest shortest path algorithm and the one you should reach for first in interviews. It works for unweighted graphs, grids ("minimum moves"), and word transformations ("Word Ladder").
Pseudocode
function bfsShortestPath(graph, src):
dist = int[V], fill with ∞
dist[src] = 0
queue = [src]
while queue not empty:
u = queue.poll()
for each neighbour v of u:
if dist[v] == ∞: // first visit = shortest
dist[v] = dist[u] + 1
queue.add(v)
return dist // O(V + E)
BFS shortest path is already covered in the BFS page. Use it for unweighted graphs. For weighted graphs, continue to Dijkstra below.
04
Section Four · Dijkstra
Dijkstra's Algorithm
Dijkstra's algorithm is BFS with a priority queue instead of a regular queue. Instead of processing vertices in FIFO order, it always processes the vertex with the smallest tentative distance. When a vertex is dequeued, its shortest distance is finalised — this greedy property holds because all edge weights are non-negative (no future path can be shorter). The algorithm: initialise all distances to ∞ except source = 0. Add (0, source) to a min-heap. Repeatedly extract the minimum, and for each neighbour, if we can improve its distance, update and add to the heap.
Pseudocode — Dijkstra
function dijkstra(graph, src):
dist = int[V], fill with ∞
dist[src] = 0
pq = MinHeap() // (distance, vertex)
pq.add(0, src)
while pq not empty:
(d, u) = pq.poll() // smallest distance if d > dist[u]: continue // stale entry — skip for each (v, weight) in graph[u]:
newDist = dist[u] + weight
if newDist < dist[v]: // relaxation
dist[v] = newDist
pq.add(newDist, v)
return dist // O((V+E) log V)
Dijkstra step-by-step on a 5-vertex graph
Common Mistake: Forgetting the stale-entry check (
if (d > dist[u]) continue;). Without it, you process the same vertex multiple times with outdated distances, potentially producing wrong answers and degrading to O(VE log V). This one line is essential.
05
Section Five · Bellman-Ford
Bellman-Ford Algorithm
Bellman-Ford handles negative edge weights by relaxing ALL edges V-1 times. Why V-1? The shortest path has at most V-1 edges — so V-1 passes are enough to propagate the shortest distance through the longest possible path. After V-1 passes, do one more: if ANY edge can still be relaxed, a negative cycle exists. Bellman-Ford is slower than Dijkstra (O(VE) vs O((V+E) log V)) but more general.
Pseudocode — Bellman-Ford
function bellmanFord(V, edges, src):
dist = int[V], fill with ∞
dist[src] = 0 // V-1 passes — relax all edges for i = 1 to V - 1:
for each edge (u, v, w) in edges:
if dist[u] != ∞ and dist[u] + w < dist[v]:
dist[v] = dist[u] + w // relax // Negative cycle detection — one more pass for each edge (u, v, w) in edges:
if dist[u] != ∞ and dist[u] + w < dist[v]:
return "negative cycle!" return dist // O(V × E)
Interview variant
Cheapest Flights Within K Stops (LC 787)
Modified Bellman-Ford: only do K+1 passes instead of V-1. At each pass, use the previous pass's distances (copy the array) to ensure you don't take more than K+1 edges. This is the classic "at most K stops" variant.
When Bellman-Ford wins
Negative Edges or Step Limits
- Negative edge weights → Dijkstra fails
- "At most K edges/stops" constraints
- Negative cycle detection
- Simpler code (no PriorityQueue)
06
Section Six · Comparison
Which Algorithm to Use
| Algorithm | Graph Type | Negative Edges | Time | Space | Use When |
|---|---|---|---|---|---|
| BFS | Unweighted | N/A | O(V+E) | O(V) | All edges weight 1 (grids, word ladder) |
| Dijkstra | Weighted, non-negative | ✗ Fails | O((V+E) log V) | O(V) | Most weighted graph problems |
| Bellman-Ford | Weighted, any | ✓ Handles | O(VE) | O(V) | Negative edges, K-stop limit |
| Floyd-Warshall | All pairs | ✓ Handles | O(V³) | O(V²) | Small V, all-pairs shortest path |
| 0-1 BFS | Weights 0 or 1 only | N/A | O(V+E) | O(V) | Binary weights (use deque) |
Decision flowchart:
- Unweighted? → BFS. Weighted, non-negative? → Dijkstra. Negative edges? → Bellman-Ford. All pairs? → Floyd-Warshall.
- Weights 0 or 1? → 0-1 BFS (deque). In interviews, 90% of shortest path problems are Dijkstra.
07
Section Seven · When to Use
Recognising Shortest Path Problems
| Signal | Algorithm | Example |
|---|---|---|
| "minimum moves/steps" on unweighted graph or grid | BFS | Word Ladder (LC 127), Shortest Bridge (LC 934) |
| "minimum cost/time" with non-negative edge weights | Dijkstra | Network Delay Time (LC 743) |
| "cheapest flight with at most K stops" | Bellman-Ford (K+1 passes) | Cheapest Flights Within K Stops (LC 787) |
| "detect negative cycle" | Bellman-Ford (V-th pass check) | Negative weight cycle detection |
| "shortest path in grid with obstacles" | BFS (unweighted) or Dijkstra (weighted) | Shortest Path in Binary Matrix (LC 1091) |
| "path with minimum effort / maximum edge" | Dijkstra (modify relaxation to track max edge) | Path With Minimum Effort (LC 1631) |
08
Section Eight · Implementation
Build It Once
Build Dijkstra once — it covers most interview problems. The structure: adjacency list with weights, dist[] array, PriorityQueue of (distance, vertex) pairs, stale-entry skip.
Java — Dijkstra (Network Delay Time)
// Network Delay Time — LC 743 — O((V+E) log V) int networkDelayTime(int[][] times, int n, int k) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] t : times)
adj.get(t[0]).add(new int[]{t[1], t[2]});
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[k] = 0;
// min-heap: (distance, node) PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] - b[0]);
pq.offer(new int[]{0, k});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
if (d > dist[u]) continue; // stale — skip for (int[] e : adj.get(u)) {
int v = e[0], w = e[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
int max = 0;
for (int i = 1; i <= n; i++) max = Math.max(max, dist[i]);
return max == Integer.MAX_VALUE ? -1 : max;
}
Shortest Path — Full Implementation
Java — All shortest path algorithms
import java.util.*;
public class ShortestPath {
// ═══ 1. Dijkstra — single source, non-negative ═ O((V+E)logV) static int[] dijkstra(List<List<int[]>> adj, int n, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
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], u = cur[1];
if (d > dist[u]) continue;
for (int[] e : adj.get(u)) {
int v = e[0], w = e[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
// ═══ 2. Bellman-Ford — handles negative edges ═ O(VE) static int[] bellmanFord(int n, int[][] edges, int src) {
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];
// negative cycle check for (int[] e : edges)
if (dist[e[0]] != Integer.MAX_VALUE
&& dist[e[0]] + e[2] < dist[e[1]])
throw new RuntimeException("Negative cycle");
return dist;
}
// ═══ 3. Cheapest Flights Within K Stops ═ O(K×E) static int findCheapestPrice(int n, int[][] flights,
int src, int dst, int k) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i <= k; i++) {
int[] prev = dist.clone(); // use PREVIOUS pass for (int[] f : flights)
if (prev[f[0]] != Integer.MAX_VALUE
&& prev[f[0]] + f[2] < dist[f[1]])
dist[f[1]] = prev[f[0]] + f[2];
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
// ═══ 4. Floyd-Warshall — all pairs ═══════ O(V³) static int[][] floydWarshall(int[][] graph, int n) {
int[][] dist = new int[n][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE / 2);
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (int[] e : graph) 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++)
dist[i][j] = Math.min(dist[i][j],
dist[i][k] + dist[k][j]);
return dist;
}
// ═══ Main ═══════════════════════════════════ public static void main(String[] args) {
// Dijkstra example List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < 5; i++) adj.add(new ArrayList<>());
adj.get(0).add(new int[]{1, 4});
adj.get(0).add(new int[]{2, 1});
adj.get(2).add(new int[]{1, 1});
adj.get(1).add(new int[]{3, 3});
adj.get(2).add(new int[]{3, 5});
adj.get(3).add(new int[]{4, 2});
System.out.println(Arrays.toString(dijkstra(adj, 5, 0)));
// [0, 2, 1, 5, 7]
}
}
Python — Shortest path algorithms
import heapq
from collections import defaultdict
# ═══ 1. Dijkstra ═════════════════════════ O((V+E)logV) def dijkstra(adj, n, src):
dist = [float('inf')] * n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue for v, w in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
# ═══ 2. Bellman-Ford ═════════════════════ O(VE) def bellman_ford(n, edges, src):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# negative cycle check for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
raise ValueError("Negative cycle")
return dist
# ═══ 3. Cheapest Flights Within K Stops ══ O(K×E) def find_cheapest(n, flights, src, dst, k):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1):
prev = dist[:]
for u, v, w in flights:
if prev[u] != float('inf') and prev[u] + w < dist[v]:
dist[v] = prev[u] + w
return dist[dst] if dist[dst] != float('inf') else -1
# ═══ 4. Floyd-Warshall ═══════════════════ O(V³) def floyd_warshall(n, edges):
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] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# Demo
adj = defaultdict(list)
adj[0] = [(1,4),(2,1)]; adj[2] = [(1,1),(3,5)]
adj[1] = [(3,3)]; adj[3] = [(4,2)]
print(dijkstra(adj, 5, 0)) # [0, 2, 1, 5, 7]
09
Section Nine · Java Reference
Use It In Java
IN JAVA — Dijkstra Idioms
Adjacency list
List<List<int[]>> adj — each int[] is {neighbour, weight} Min-heap
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]); Heap entry
new int[]{distance, vertex} — distance first for comparator | Pattern | Java Code | Note |
|---|---|---|
| Init distances | Arrays.fill(dist, Integer.MAX_VALUE); | ∞ sentinel — guard against overflow when adding |
| Stale check | if (d > dist[u]) continue; | ESSENTIAL — skip outdated heap entries |
| Relax edge | if (dist[u] + w < dist[v]) | Only update if strictly shorter |
| Add to heap | pq.offer(new int[]{dist[v], v}); | Lazy deletion — don't remove old entries |
| BF copy array | int[] prev = dist.clone(); | For K-stops: use PREVIOUS pass's distances |
⚠ Gotcha:
Integer.MAX_VALUE + anything overflows to a negative number, which is "less than" the current distance — causing a wrong relaxation. Guard with: if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]). Or use Integer.MAX_VALUE / 2 as the sentinel to avoid overflow entirely.
⚠ Gotcha: Java's
PriorityQueue does NOT support decrease-key. Instead, we use "lazy deletion" — add a new entry with the updated distance and skip stale entries when polled. This is why the stale check (d > dist[u]) is critical.
⚠ Gotcha: For Cheapest Flights (LC 787), you MUST clone the dist array (
dist.clone()) at the start of each pass. Without cloning, a single pass can relax a chain of edges (using distances updated THIS pass), effectively using more than K stops.
10
Section Ten · Practice
Problems To Solve
Shortest path interviews test two things: (1) choosing the right algorithm (BFS vs Dijkstra vs Bellman-Ford), and (2) implementing Dijkstra cleanly with the stale-entry check. Practice Network Delay Time first — it's the purest Dijkstra template — then move to the variants.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | dijkstra | Network Delay Time — LC 743 | Pure Dijkstra from source. Answer = max distance to any node. Return -1 if any node is unreachable. |
| Medium | bellman-ford | Cheapest Flights Within K Stops — LC 787 | Modified Bellman-Ford: K+1 passes with array cloning. Or BFS with level tracking. Or Dijkstra with (cost, node, stops) tuples. |
| Medium | dijkstra | Path With Minimum Effort — LC 1631 | Grid Dijkstra where "distance" = max absolute height difference along the path. Modified relaxation: max(dist[u], |h[u]-h[v]|). |
| Medium | bfs | Shortest Path in Binary Matrix — LC 1091 | BFS on a grid (8-directional). Unweighted = BFS is optimal. Return -1 if blocked. |
| Medium | dijkstra | Swim in Rising Water — LC 778 | Grid Dijkstra where cost = max elevation along the path. Modified relaxation: max(dist[u], grid[v]). |
| Hard | dijkstra | Shortest Path Visiting All Nodes — LC 847 | BFS/Dijkstra with bitmask state: (current node, visited set). State space = V × 2^V. |
Interview Pattern:
- See "minimum cost / minimum time / minimum effort"? → Dijkstra (non-negative weights) or Bellman-Ford (negative or K-stops).
- See "minimum steps / minimum moves" on unweighted graph/grid? → BFS.
- The template: dist[] + PriorityQueue + stale check + relaxation.
- After building it once, every shortest path problem is a variation of the same 15 lines.