Shortest Path Algorithms
Overview: Which Algorithm to Use?
ALGORITHM GRAPH TYPE TIME SPACE ─────────────────────────────────────────────────────────────────────── BFS Unweighted (all w=1) O(V + E) O(V) DAG shortest path Weighted DAG O(V + E) O(V) Dijkstra (heap) Weighted, NO neg edges O((V+E) log V) O(V) Dijkstra (array) Weighted, NO neg edges O(V²) O(V) Bellman-Ford Weighted, neg OK O(V × E) O(V) Floyd-Warshall All-pairs, any weights O(V³) O(V²) QUICK DECISION: No weights (BFS) → BFS Weighted, positive, single source → Dijkstra Weighted, negative edges possible → Bellman-Ford All-pairs shortest paths → Floyd-Warshall DAG (topological order) → DAG shortest path O(V+E) Negative cycle detection → Bellman-Ford (Vth iteration check)
Algorithm 1: BFS (Unweighted Graphs)
When all edges have equal weight (or weight 1), BFS gives shortest paths in O(V+E) — the fastest possible for this case.
Unweighted graph:
0 ─── 1 ─── 3
│ │
2 ─── 4 ─── 5
BFS from 0:
Level 0: {0} dist[0]=0
Level 1: {1,2} dist[1]=1, dist[2]=1
Level 2: {3,4} dist[3]=2, dist[4]=2
Level 3: {5} dist[5]=3
Shortest distances from 0: [0, 1, 1, 2, 2, 3]
(Full BFS implementation covered in the BFS topic — see Graph BFS)
Algorithm 2: Dijkstra's Algorithm
For weighted graphs with non-negative edge weights. Uses a min-heap to always process the currently closest unvisited vertex.
CORE IDEA:
Maintain distance array dist[] — dist[v] = best known distance from source to v.
Use a min-heap to extract the vertex with the smallest current distance.
Relax all its edges: if dist[u] + weight(u,v) < dist[v], update dist[v].
Once a vertex is extracted (settled), its distance is FINAL.
GREEDY INVARIANT: when vertex u is extracted from the heap,
dist[u] is the shortest path from source to u.
(Holds only for non-negative weights!)
Weighted graph for Dijkstra dry run:
0 ──4── 1
│ │\
8 2 5
│ │ \
7 ──9── 6──2──5
\ /
2─4
(simplified)
Let's use a clean 5-vertex example:
0──4──1, 0──8──7, 1──8──2, 1──11──7,
2──7──3, 2──2──8, 2──4──5, 7──1──6,
7──7──8, 6──2──5, 8──6──6, 3──9──4, 3──14──5, 4──10──5
Actually using simpler example:
Vertices: 0-4
Edges: (0,1,4),(0,2,1),(1,3,1),(2,1,2),(2,3,5),(3,4,3)
0 ──4── 1
│ │
1 1
│ │
2 ──2── 1 (via 2)
│
5
│
3 ──3── 4
Cleaner: 0→1:4, 0→2:1, 2→1:2, 1→3:1, 2→3:5, 3→4:3
Dijkstra from source=0:
dist = [0, ∞, ∞, ∞, ∞]
heap = [(0, 0)]
Extract (0,0): u=0
Edge 0→1 weight 4: dist[1]=min(∞,0+4)=4, push (4,1)
Edge 0→2 weight 1: dist[2]=min(∞,0+1)=1, push (1,2)
dist = [0, 4, 1, ∞, ∞]
Extract (1,2): u=2 ← closest unvisited
Edge 2→1 weight 2: dist[1]=min(4,1+2)=3, push (3,1) ← shorter!
Edge 2→3 weight 5: dist[3]=min(∞,1+5)=6, push (6,3)
dist = [0, 3, 1, 6, ∞]
Extract (3,1): u=1
Edge 1→3 weight 1: dist[3]=min(6,3+1)=4, push (4,3) ← shorter!
dist = [0, 3, 1, 4, ∞]
Extract (4,1): u=1 → already settled (dist[1]=3 < 4), skip stale entry
Extract (4,3): u=3
Edge 3→4 weight 3: dist[4]=min(∞,4+3)=7, push (7,4)
dist = [0, 3, 1, 4, 7]
Extract (6,3): stale (dist[3]=4 < 6), skip
Extract (7,4): u=4, no outgoing edges
dist = [0, 3, 1, 4, 7]
Final shortest distances from 0: [0, 3, 1, 4, 7]
1import java.util.*;
2
3public class Dijkstra {
4
5 public static int[] dijkstra(int V,
6 List<List<int[]>> adj, // adj[u] = [[v, w], ...]
7 int source) {
8 int[] dist = new int[V];
9 Arrays.fill(dist, Integer.MAX_VALUE);
10 dist[source] = 0;
11
12 // Min-heap: [distance, vertex]
13 PriorityQueue<int[]> pq = new PriorityQueue<>(
14 Comparator.comparingInt(a -> a[0])
15 );
16 pq.offer(new int[]{0, source});
17
18 while (!pq.isEmpty()) {
19 int[] curr = pq.poll();
20 int d = curr[0], u = curr[1];
21
22 // Skip stale entries (distance outdated)
23 if (d > dist[u]) continue;
24
25 for (int[] edge : adj.get(u)) {
26 int v = edge[0], w = edge[1];
27
28 if (dist[u] + w < dist[v]) {
29 dist[v] = dist[u] + w;
30 pq.offer(new int[]{dist[v], v});
31 }
32 }
33 }
34
35 return dist;
36 }
37
38 // Dijkstra with path reconstruction
39 public static int[] dijkstraWithPath(int V, List<List<int[]>> adj,
40 int source, int target) {
41 int[] dist = new int[V];
42 int[] parent = new int[V];
43 Arrays.fill(dist, Integer.MAX_VALUE);
44 Arrays.fill(parent, -1);
45 dist[source] = 0;
46
47 PriorityQueue<int[]> pq = new PriorityQueue<>(
48 Comparator.comparingInt(a -> a[0])
49 );
50 pq.offer(new int[]{0, source});
51
52 while (!pq.isEmpty()) {
53 int[] curr = pq.poll();
54 int d = curr[0], u = curr[1];
55 if (d > dist[u]) continue;
56
57 for (int[] edge : adj.get(u)) {
58 int v = edge[0], w = edge[1];
59 if (dist[u] + w < dist[v]) {
60 dist[v] = dist[u] + w;
61 parent[v] = u;
62 pq.offer(new int[]{dist[v], v});
63 }
64 }
65 }
66
67 // Reconstruct path from target to source
68 List<Integer> path = new ArrayList<>();
69 for (int v = target; v != -1; v = parent[v]) path.add(0, v);
70 System.out.println("Shortest path: " + path + ", distance: " + dist[target]);
71 return dist;
72 }
73
74 public static void main(String[] args) {
75 int V = 5;
76 List<List<int[]>> adj = new ArrayList<>();
77 for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
78
79 // Directed weighted edges: 0→1:4, 0→2:1, 2→1:2, 1→3:1, 2→3:5, 3→4:3
80 adj.get(0).add(new int[]{1, 4});
81 adj.get(0).add(new int[]{2, 1});
82 adj.get(2).add(new int[]{1, 2});
83 adj.get(1).add(new int[]{3, 1});
84 adj.get(2).add(new int[]{3, 5});
85 adj.get(3).add(new int[]{4, 3});
86
87 int[] dist = dijkstra(V, adj, 0);
88 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));
89 // [0, 3, 1, 4, 7]
90
91 dijkstraWithPath(V, adj, 0, 4);
92 // Shortest path: [0, 2, 1, 3, 4], distance: 7
93 }
94}Output:
Shortest distances from 0: [0, 3, 1, 4, 7]
Shortest path: [0, 2, 1, 3, 4], distance: 7
Algorithm 3: Bellman-Ford
Handles negative edge weights. Relaxes ALL edges V-1 times. Can detect negative cycles.
CORE IDEA:
After k iterations, dist[v] = shortest path from source to v using ≤ k edges.
After V-1 iterations: all simple paths (≤ V-1 edges) are found.
A Vth iteration that still reduces a distance → negative cycle exists.
RELAXATION:
for each edge (u, v, weight):
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
Graph with negative edge:
0──1──1, 0──4──2, 1─(–3)──3, 2──2──3, 3──1──4
Dist from 0: After iter 1: After iter 2: After iter 3:
[0,∞,∞,∞,∞] [0,1,4,∞,∞] [0,1,4,−2,∞] [0,1,4,−2,−1]
Edge 1→3 weight -3 creates shortest path 0→1→3 (cost 1+(-3)=-2)
Even though 3 has more edges, its weight is lower.
Dijkstra would FAIL here — it would settle vertex 2 before vertex 1,
and then 3 would get dist 4+2=6 before the negative path 1→3 is found.
1import java.util.*;
2
3public class BellmanFord {
4
5 // Edge representation for Bellman-Ford
6 static class Edge {
7 int u, v, weight;
8 Edge(int u, int v, int w) { this.u = u; this.v = v; this.weight = w; }
9 }
10
11 public static int[] bellmanFord(int V, List<Edge> edges, int source) {
12 int[] dist = new int[V];
13 Arrays.fill(dist, Integer.MAX_VALUE);
14 dist[source] = 0;
15
16 // Relax ALL edges V-1 times
17 for (int i = 0; i < V - 1; i++) {
18 boolean updated = false; // Early termination optimisation
19
20 for (Edge e : edges) {
21 if (dist[e.u] != Integer.MAX_VALUE &&
22 dist[e.u] + e.weight < dist[e.v]) {
23 dist[e.v] = dist[e.u] + e.weight;
24 updated = true;
25 }
26 }
27
28 if (!updated) break; // Converged early — no more relaxation needed
29 }
30
31 // V-th relaxation: check for negative cycles
32 for (Edge e : edges) {
33 if (dist[e.u] != Integer.MAX_VALUE &&
34 dist[e.u] + e.weight < dist[e.v]) {
35 System.out.println("Negative cycle detected!");
36 return null;
37 }
38 }
39
40 return dist;
41 }
42
43 public static void main(String[] args) {
44 int V = 5;
45 List<Edge> edges = new ArrayList<>();
46 // Graph: 0→1:1, 0→2:4, 1→3:-3, 2→3:2, 3→4:1
47 edges.add(new Edge(0, 1, 1));
48 edges.add(new Edge(0, 2, 4));
49 edges.add(new Edge(1, 3, -3));
50 edges.add(new Edge(2, 3, 2));
51 edges.add(new Edge(3, 4, 1));
52
53 int[] dist = bellmanFord(V, edges, 0);
54 if (dist != null) {
55 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));
56 // [0, 1, 4, -2, -1]
57 }
58
59 // Test negative cycle detection: 0→1:1, 1→2:-2, 2→0:0 (negative cycle)
60 List<Edge> cycleEdges = new ArrayList<>();
61 cycleEdges.add(new Edge(0, 1, 1));
62 cycleEdges.add(new Edge(1, 2, -2));
63 cycleEdges.add(new Edge(2, 0, 0)); // Total cycle weight = 1-2+0 = -1 < 0
64 bellmanFord(3, cycleEdges, 0); // Prints "Negative cycle detected!"
65 }
66}Output:
Shortest distances from 0: [0, 1, 4, -2, -1]
Negative cycle detected!
Algorithm 4: Floyd-Warshall (All-Pairs)
Computes shortest paths between every pair of vertices in O(V³). Works with negative edges but not negative cycles.
CORE IDEA:
dist[i][j] = shortest path from i to j.
Try every vertex k as an intermediate vertex:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
After considering all k, dist[i][j] = true shortest path.
Initialisation:
dist[i][i] = 0 for all i
dist[i][j] = edge weight if edge (i,j) exists
dist[i][j] = ∞ otherwise
Example (4 vertices):
0──3──1
│ │
7 2
│ │
3──5──2
Weights: 0→1:3, 0→3:7, 1→2:2, 3→1:... (simplified)
After Floyd-Warshall: dist[i][j] = shortest path i to j considering all routes.
NEGATIVE CYCLE CHECK:
After algorithm completes: if dist[i][i] < 0 for any i → negative cycle.
1import java.util.Arrays;
2
3public class FloydWarshall {
4
5 public static int[][] floydWarshall(int V, int[][] graph) {
6 // Copy input (graph[i][j] = weight or INF if no edge)
7 int[][] dist = new int[V][V];
8 final int INF = Integer.MAX_VALUE / 2; // Avoid overflow in addition
9
10 for (int i = 0; i < V; i++) {
11 for (int j = 0; j < V; j++) {
12 dist[i][j] = graph[i][j];
13 }
14 }
15
16 // Try each vertex k as intermediate
17 for (int k = 0; k < V; k++) {
18 for (int i = 0; i < V; i++) {
19 for (int j = 0; j < V; j++) {
20 // Skip if i→k or k→j is unreachable
21 if (dist[i][k] == INF || dist[k][j] == INF) continue;
22 dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
23 }
24 }
25 }
26
27 // Negative cycle detection
28 for (int i = 0; i < V; i++) {
29 if (dist[i][i] < 0) {
30 System.out.println("Negative cycle detected!");
31 return null;
32 }
33 }
34
35 return dist;
36 }
37
38 public static void main(String[] args) {
39 final int INF = Integer.MAX_VALUE / 2;
40 int V = 4;
41
42 // graph[i][j] = direct edge weight (INF = no edge)
43 int[][] graph = {
44 { 0, 3, INF, 7},
45 { 8, 0, 2, INF},
46 { 5, INF, 0, 1},
47 { 2, INF, INF, 0}
48 };
49
50 int[][] dist = floydWarshall(V, graph);
51 if (dist != null) {
52 System.out.println("All-pairs shortest paths:");
53 for (int[] row : dist) {
54 for (int d : row) System.out.printf("%5s", d == INF ? "∞" : d);
55 System.out.println();
56 }
57 }
58 }
59}Output (Floyd-Warshall — all pairs from 4-vertex example):
0 3 5 6
8 0 2 3
5 8 0 1
2 5 7 0
Shortest path 1→3: 3 (1→2→3 has weight 2+1=3 < direct path)
Algorithm 5: Shortest Path in DAG (O(V+E))
For Directed Acyclic Graphs, topological order processing gives O(V+E) shortest paths — faster than Dijkstra.
ALGORITHM:
1. Find topological order of vertices.
2. Initialize dist[source]=0, dist[others]=∞.
3. Process vertices in topological order:
For each vertex u (in topo order):
For each edge u→v with weight w:
If dist[u]+w < dist[v]: dist[v] = dist[u]+w
WHY IT WORKS:
When we process u in topological order, all vertices that could
provide a shorter path to u have already been processed.
So dist[u] is already the shortest path when we process u.
No priority queue needed — topological order gives the correct
processing sequence automatically.
DAG: 0→1:5, 0→3:3, 1→2:6, 1→3:2, 2→4:7, 3→1:4, 3→2:8, 3→4:2, 4→5:3
Topological order: [0, 3, 1, 2, 4, 5] (one valid ordering)
dist = [0, ∞, ∞, ∞, ∞, ∞]
Process 0: 0→1: dist[1]=min(∞,0+5)=5; 0→3: dist[3]=min(∞,0+3)=3
dist = [0, 5, ∞, 3, ∞, ∞]
Process 3: 3→1: dist[1]=min(5,3+4)=5 (no change); 3→2: dist[2]=min(∞,3+8)=11; 3→4: dist[4]=min(∞,3+2)=5
dist = [0, 5, 11, 3, 5, ∞]
Process 1: 1→2: dist[2]=min(11,5+6)=11 (no change); 1→3: 3 already processed
Process 2: 2→4: dist[4]=min(5,11+7)=5 (no change)
Process 4: 4→5: dist[5]=min(∞,5+3)=8
Process 5: no outgoing edges
Final: [0, 5, 11, 3, 5, 8]
1import java.util.*;
2
3public class DAGShortestPath {
4
5 public static int[] dagShortestPath(int V,
6 List<List<int[]>> adj,
7 int source) {
8 // Step 1: Topological sort (DFS post-order)
9 boolean[] visited = new boolean[V];
10 Stack<Integer> topoStack = new Stack<>();
11
12 for (int i = 0; i < V; i++) {
13 if (!visited[i]) topoHelper(i, adj, visited, topoStack);
14 }
15
16 // Step 2: Initialize distances
17 int[] dist = new int[V];
18 Arrays.fill(dist, Integer.MAX_VALUE);
19 dist[source] = 0;
20
21 // Step 3: Relax edges in topological order
22 while (!topoStack.isEmpty()) {
23 int u = topoStack.pop();
24
25 if (dist[u] != Integer.MAX_VALUE) {
26 for (int[] edge : adj.get(u)) {
27 int v = edge[0], w = edge[1];
28 if (dist[u] + w < dist[v]) {
29 dist[v] = dist[u] + w;
30 }
31 }
32 }
33 }
34
35 return dist;
36 }
37
38 private static void topoHelper(int u, List<List<int[]>> adj,
39 boolean[] visited, Stack<Integer> stack) {
40 visited[u] = true;
41 for (int[] edge : adj.get(u)) {
42 if (!visited[edge[0]]) topoHelper(edge[0], adj, visited, stack);
43 }
44 stack.push(u);
45 }
46
47 public static void main(String[] args) {
48 int V = 6;
49 List<List<int[]>> adj = new ArrayList<>();
50 for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
51
52 adj.get(0).add(new int[]{1, 5}); adj.get(0).add(new int[]{3, 3});
53 adj.get(1).add(new int[]{2, 6}); adj.get(1).add(new int[]{3, 2});
54 adj.get(2).add(new int[]{4, 7});
55 adj.get(3).add(new int[]{1, 4}); adj.get(3).add(new int[]{2, 8}); adj.get(3).add(new int[]{4, 2});
56 adj.get(4).add(new int[]{5, 3});
57
58 int[] dist = dagShortestPath(V, adj, 0);
59 System.out.println("DAG Shortest distances from 0: " + Arrays.toString(dist));
60 // [0, 5, 11, 3, 5, 8]
61 }
62}Output:
DAG Shortest distances from 0: [0, 5, 11, 3, 5, 8]
Algorithm Comparison
BFS DAG SP Dijkstra Bellman-Ford Floyd-Warshall
─────────────────────────────────────────────────────────────
Time O(V+E) O(V+E) O((V+E)logV) O(V·E) O(V³)
Space O(V) O(V) O(V) O(V) O(V²)
Negative edges ✗ ✓ ✗ ✓ ✓
Negative cycles ✗ N/A N/A Detects Detects
Graph type Unwt DAG only Any (no neg) Any Any
Single/All pairs Single Single Single Single ALL pairs
Works on Unwt DAG Pos. weights Any weights Any weights
BEST CHOICE:
Unweighted graph (BFS = edges of weight 1) → BFS
Positive weights, single source → Dijkstra (heap)
Negative weights, single source → Bellman-Ford
All pairs, small graph (V ≤ 500) → Floyd-Warshall
DAG, any weights → DAG Shortest Path (O(V+E))
Dense graph (E ≈ V²), positive weights → Dijkstra with array O(V²)
Complexity Summary
| Algorithm | Time | Space | Handles Negatives | Multi-source |
|---|---|---|---|---|
| BFS | O(V + E) | O(V) | No (weight=1) | Yes |
| DAG SP | O(V + E) | O(V) | Yes | No |
| Dijkstra (heap) | O((V+E) log V) | O(V) | No | No |
| Dijkstra (array) | O(V²) | O(V) | No | No |
| Bellman-Ford | O(V × E) | O(V) | Yes | No |
| Floyd-Warshall | O(V³) | O(V²) | Yes | All pairs |
Common Mistakes
Using Dijkstra's on graphs with negative edges. The greedy "settle once" invariant breaks — a settled vertex can be improved later via a negative edge. Use Bellman-Ford when any edge weight is negative. Dijkstra gives incorrect results silently (no error, just wrong distances).
Bellman-Ford: forgetting to skip unreachable sources. If dist[u] == INT_MAX, relaxing edge u→v adds INT_MAX + weight → integer overflow or arbitrary values. Always check dist[u] != INT_MAX before relaxing.
Floyd-Warshall: using INT_MAX as infinity causes overflow. dist[i][k] + dist[k][j] where both are INT_MAX overflows to a negative number. Use INT_MAX / 2 as the infinity sentinel, or check for INF before adding.
Dijkstra: not skipping stale heap entries. The heap may contain multiple entries for the same vertex with outdated (larger) distances. Without the check if d > dist[u]: continue, stale entries cause redundant relaxations and wrong results in some implementations.
DAG shortest path: running on a cyclic graph. The topological sort step will produce incorrect ordering for cyclic graphs (some vertices may never appear). Always verify the graph is acyclic before using the DAG shortest path algorithm.
Interview Questions
Q: Why can't Dijkstra's handle negative edge weights?
Dijkstra's key invariant: once a vertex is extracted from the min-heap, its distance is final and optimal. With only non-negative edges, no future path can make it shorter (adding more edges can only increase or maintain distance). With negative edges, a future path through a negative edge could provide a shorter route to an already-settled vertex — breaking the invariant. Example: vertex A settled at distance 5. Later we find path through B→A with weight -10, giving distance 3. But A is already settled — Dijkstra misses this shorter path.
Q: Bellman-Ford does V-1 iterations. What happens in a Vth iteration?
After V-1 iterations, all simple shortest paths (using at most V-1 edges) are found. If a Vth iteration still improves some distance dist[v], it means v can be reached via a path with more than V-1 edges — only possible if the path contains a repeated vertex, forming a cycle. If the cycle has negative total weight, dist[v] keeps decreasing — a negative cycle. This is how Bellman-Ford detects negative cycles: any improvement in the Vth iteration signals a negative cycle reachable from the source.
Q: When is Floyd-Warshall better than running Dijkstra from every vertex?
Floyd-Warshall runs in O(V³). Running Dijkstra from every vertex (V times) with a heap takes O(V × (V+E) log V). For dense graphs (E ≈ V²): V × V² log V = O(V³ log V) — Floyd-Warshall is faster. For sparse graphs (E ≈ V): V × V log V = O(V² log V) — repeated Dijkstra is faster. Additionally, Floyd-Warshall's implementation is simpler (3 nested loops). Also, Floyd-Warshall handles negative edges (without negative cycles), while Dijkstra doesn't — so for graphs with negative edges, Floyd-Warshall is the only all-pairs option.
Summary
Five shortest path algorithms for different scenarios:
BFS — unweighted graphs only; O(V+E); guaranteed shortest by edge count.
Dijkstra's — weighted graphs, no negative edges; O((V+E) log V) with heap; greedy — settle closest unvisited vertex first.
Bellman-Ford — any weights including negative; O(V×E); relax all edges V-1 times; Vth iteration detects negative cycles.
Floyd-Warshall — all-pairs shortest paths; O(V³) time, O(V²) space; works with negative edges; check dist[i][i] < 0 for negative cycles.
DAG Shortest Path — DAG only, any weights; O(V+E); topological sort processing eliminates need for priority queue.
Key rules:
- ›No weights → BFS
- ›Positive weights → Dijkstra
- ›Negative weights → Bellman-Ford
- ›All pairs → Floyd-Warshall
- ›DAG, any weights → DAG shortest path
In the next topic you will explore Minimum Spanning Tree — Kruskal's and Prim's algorithms for finding the minimum-weight tree connecting all vertices.
Dijkstra's algorithm fails on graphs with negative edge weights. Why?