| Node | Known Distance | Previous Hop | Status |
|---|---|---|---|
| ASTART | 0 | — | Reachable |
| B | ∞ | — | Unvisited |
| C | ∞ | — | Unvisited |
| D | ∞ | — | Unvisited |
| E | ∞ | — | Unvisited |
| F | ∞ | — | Unvisited |
The Bellman-Ford algorithm is a dynamic programming powerhouse designed to compute Single-Source Shortest Paths (SSSP) on weighted directed graphs. Unlike greedy alternatives like Dijkstra, Bellman-Ford safely handles negative edge weights and definitively detects negative weight cycles.
Dijkstra makes permanent greedy commitments that fail when negative shortcuts appear later. Bellman-Ford repeatedly relaxes all edges, guaranteeing optimal distances even with negative tolls or voucher discounts.
If a graph has a cycle whose net sum of edge weights is negative, shortest paths are theoretically -∞. Bellman-Ford detects this during pass V if any edge can still be relaxed.
In financial currency exchange markets, converting exchange rates via -log(rate) transforms multiplicative exchange yields into additive shortest paths, allowing algorithmic traders to detect arbitrage loops instantly.
Understanding the worst-case edge relaxation propagation through a concrete example:
Consider a simple line graph with 4 nodes and edge weights of 1:
Initially: dist[A] = 0 and dist[B] = ∞, dist[C] = ∞, dist[D] = ∞.
In Bellman-Ford, a "loop" iterates through every edge in our edge array. But we cannot guarantee the ordering of edges in memory! Suppose the edges are stored in the absolute worst-case order (Right-to-Left):
[ Edge(C ➔ D), Edge(B ➔ C), Edge(A ➔ B) ]| Loop # | Edge Inspected | Relaxation Condition | Result | Distances at End of Loop |
|---|---|---|---|---|
| Loop 1 | C ➔ D | dist[C] is ∞ + 1 = ∞ ≮ ∞ | No change (D = ∞) | A: 0, B: 1, C: ∞, D: ∞ |
| B ➔ C | dist[B] is ∞ + 1 = ∞ ≮ ∞ | No change (C = ∞) | ||
| A ➔ B | dist[A] is 0 + 1 = 1 < ∞ | ⚡ B updated to 1! | ||
| Loop 2 | C ➔ D | dist[C] is still ∞ | No change (D = ∞) | A: 0, B: 1, C: 2, D: ∞ |
| B ➔ C | dist[B] is 1 + 1 = 2 < ∞ | ⚡ C updated to 2! | ||
| A ➔ B | 0 + 1 = 1 == 1 | Already optimal | ||
| Loop 3 (V - 1) | C ➔ D | dist[C] is 2 + 1 = 3 < ∞ | ⚡ D updated to 3! | A: 0, B: 1, C: 2, D: 3 |
| B ➔ C | 1 + 1 = 2 == 2 | Already optimal | ||
| A ➔ B | 0 + 1 = 1 == 1 | Already optimal |
In the worst-case edge order, each loop can only advance the shortest path "wave" by exactly 1 edge forward. Since the longest simple path in a graph with \(V\) vertices has \(V - 1\) edges, we strictly require \(|V| - 1\) loops to guarantee that all vertices have received their optimal shortest distance!
When to use each algorithm in technical interviews and system design:
| Algorithm | Scope | Time Complexity | Negative Weights? | Negative Cycle Detection? |
|---|---|---|---|---|
| Bellman-Ford | Single-Source (1 to All) | O(V · E) | ✅ Yes | ✅ Yes (Pass V) |
| Dijkstra (Min-Heap) | Single-Source (1 to All) | O((V + E) log V) | ❌ No (Non-negative only) | ❌ No (May infinite loop) |
| Floyd-Warshall | All-Pairs (All to All) | O(V³) | ✅ Yes | ✅ Yes (Check dist[i][i] < 0) |
| BFS (Unweighted) | Single-Source (1 to All) | O(V + E) | N/A (Unweighted only) | N/A |
Direct Bellman-Ford variant! Instead of V - 1 passes, run exactly k + 1 passes with an immutable copy of distances per pass.
Keep a boolean flag updated per pass. If 0 edges are relaxed, terminate immediately to save unnecessary O(V · E) cycles.
When solving constrained hop problems, always clone temp_dist = dist[:] before each pass to prevent multi-hop cascades in a single iteration.
Routing Information Protocol (RIP) uses Bellman-Ford in network routers where each router shares distance vectors with immediate neighbors.
Key interview questions on Bellman-Ford:
Dijkstra greedily marks a node as permanently visited the moment it is extracted from the priority queue, assuming no future path can be shorter. If a negative weight edge appears later, Dijkstra cannot backtrack to update already locked nodes, resulting in incorrect shortest distances.
A directed cycle whose total sum of edge weights is strictly negative (< 0). By continuously looping around this cycle, you can reduce the path length to -∞. Hence, no finite shortest path exists.
Time Complexity: O(V · E) because we perform at most V-1 passes over all E edges.
Space Complexity: O(V) to store the distance array and predecessor map.