Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall & Johnson
“Non-negative edge Dijkstra, negative edge relaxation, negative cycle detection, and all-pairs dynamic programming.”
1.Single-Source Shortest Paths: Dijkstra vs Bellman-Ford
§ 4.1.For a weighted graph G = (V, E, w), the shortest-path weight from s to v is delta(s, v).
Edge Relaxation Invariant:
Relax(u, v, w): If dist[v] > dist[u] + w(u, v), update dist[v] = dist[u] + w(u, v).
Dijkstra's Algorithm (Non-Negative Weights Only):
Maintains a set of vertices whose final shortest-path weights have been determined. Greedily extracts min dist[u] vertex from priority queue.
Complexity: O((V + E) log V) using binary min-heap.
Bellman-Ford Algorithm (General Weights):
Relaxes all |E| edges |V| - 1 times. A shortest simple path contains at most |V| - 1 edges. If a |V|-th pass further relaxes any edge, a negative-weight cycle exists.
Complexity: O(V * E).
2.All-Pairs Shortest Paths: Floyd-Warshall & Johnson's Reweighting
§ 4.2.Floyd-Warshall (Dense Graphs, Dynamic Programming):
Considers intermediate vertices in {1, 2, ..., k}.
d_{ij}^{(k)} = min( d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)} ).
Time complexity: Theta(V^3), space Theta(V^2).
Johnson's Algorithm (Sparse Graphs with Negative Weights):
1. Add dummy vertex s with 0-weight edges to all v in V.
2. Run Bellman-Ford from s to compute potential function h(v) = delta(s, v).
3. Reweight edges: hat{w}(u, v) = w(u, v) + h(u) - h(v). By triangle inequality, hat{w}(u, v) >= 0.
4. Run Dijkstra from every vertex u using non-negative weights hat{w}.
5. Recover true distances: delta(u, v) = hat{delta}(u, v) - h(u) + h(v).
Complexity: O(V^2 log V + V E).
3. Worked Problem: Floyd-Warshall Matrix Update Iteration
At step k, the k-th row and k-th column of the distance matrix never change because d[k, k] = 0.
Problem: A 3-vertex directed graph has adjacency weight matrix D^{(0)}:
[ 0, 4, inf ]
[ inf, 0, 1 ]
[ 2, inf, 0 ]
Compute D^{(1)} (using vertex 1 as intermediate) and D^{(2)} (using vertex 2 as intermediate).
Step 1: Compute D^{(1)} (intermediate vertex k = 1):
Formula: D^{(1)}[i, j] = min( D^{(0)}[i, j], D^{(0)}[i, 1] + D^{(0)}[1, j] )
Row 1 and Col 1 remain unchanged.
- D^{(1)}[2, 3] = min(1, D^{(0)}[2, 1] + D^{(0)}[1, 3]) = min(1, inf + inf) = 1.
- D^{(1)}[3, 2] = min(inf, D^{(0)}[3, 1] + D^{(0)}[1, 2]) = min(inf, 2 + 4) = 6.
D^{(1)} matrix:
[ 0, 4, inf ]
[ inf, 0, 1 ]
[ 2, 6, 0 ]
Step 2: Compute D^{(2)} (intermediate vertex k = 2):
Formula: D^{(2)}[i, j] = min( D^{(1)}[i, j], D^{(1)}[i, 2] + D^{(1)}[2, j] )
Row 2 and Col 2 remain unchanged.
- D^{(2)}[1, 3] = min(inf, D^{(1)}[1, 2] + D^{(1)}[2, 3]) = min(inf, 4 + 1) = 5.
- D^{(2)}[3, 1] = min(2, D^{(1)}[3, 2] + D^{(1)}[2, 1]) = min(2, 6 + inf) = 2.
D^{(2)} matrix:
[ 0, 4, 5 ]
[ inf, 0, 1 ]
[ 2, 6, 0 ]
Step 3: Verification:
Direct path 1 -> 2 -> 3 has cost 4 + 1 = 5, replacing previous distance of infinity. Fully verified.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Best visual explanations of algorithm design and complexity analysis.
Exam-focused with GATE PYQ numericals on every major algorithm.