Loading learning content...
The Bellman-Ford algorithm's core is remarkably simple—deceptively so. While Dijkstra requires a carefully ordered priority queue and delicate invariant maintenance, Bellman-Ford reduces to three nested loops: iterate V-1 times, and in each iteration, relax every edge in the graph.
This brute-force simplicity isn't a sign of naive design—it's a profound insight. By relaxing every edge V-1 times, regardless of order, we guarantee that shortest paths propagate correctly from the source to every reachable vertex. No sophisticated data structures. No greedy assumptions. Just methodical, exhaustive relaxation.
By the end of this page, you will deeply understand the relaxation operation, why exactly V-1 iterations are necessary and sufficient, and be able to trace through Bellman-Ford's execution step-by-step on any graph. You'll also understand the critical path length invariant that guarantees correctness.
Before examining Bellman-Ford's full algorithm, let's deeply understand the relaxation operation—the atomic building block shared by Dijkstra, Bellman-Ford, and other shortest path algorithms.
The Relaxation Definition:
For an edge from vertex u to vertex v with weight w(u, v):
RELAX(u, v, w):
if dist[v] > dist[u] + w(u, v):
dist[v] = dist[u] + w(u, v)
predecessor[v] = u
What relaxation means intuitively:
Imagine dist[v] as the best-known distance from the source to v. Relaxation asks: 'Can I improve my path to v by going through u instead of my current path?'
dist[u] is the best-known distance to udist[u] + w(u, v) is the distance to v if we go through udist[v], we've found a shorter path—update it!The term 'relaxation' comes from optimization theory and physics. Think of the distance estimates as tension in a system. Initially, we over-estimate all distances (infinite tension). Each relaxation 'relaxes' this tension by lowering an over-estimate. When no more relaxation is possible, the system is at its optimal (minimal tension) state, and all distances are correct.
Mathematical Properties of Relaxation:
Property 1: Relaxation only improves estimates
Relaxation can only decrease dist[v] (or leave it unchanged). It never increases distances. This guarantees monotonic progress toward the optimal solution.
Property 2: Relaxation maintains the optimality invariant
If dist[u] equals the true shortest path distance to u, and we relax edge (u, v), then afterward dist[v] is at most the true shortest path distance to v using paths that go through u as the last intermediate vertex.
Property 3: Safe operation
Relaxation is always 'safe'—it never produces incorrect results, only insufficient ones. You can relax an edge any number of times; if no improvement is possible, nothing happens.
The path-length invariant:
Here's the critical insight that makes Bellman-Ford work: after k iterations of relaxing all edges, dist[v] is optimal for all vertices v whose shortest path from the source has at most k edges.
This is a classic proof by induction. Base case: after 0 iterations, only dist[source] = 0 is correct. Inductive step: if all k-edge shortest paths are correct after iteration k, then iteration k+1 correctly computes all (k+1)-edge shortest paths by relaxing the final edge. Since simple paths have at most V-1 edges, V-1 iterations cover all cases.
With the relaxation operation and the path-length invariant established, the complete Bellman-Ford algorithm is elegantly straightforward:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
def bellman_ford(graph, source): """ Finds shortest paths from source to all vertices. Args: graph: Dict mapping vertex -> list of (neighbor, weight) tuples source: Starting vertex Returns: (dist, pred): Distance dict and predecessor dict Returns None if negative cycle detected """ # Get all vertices vertices = list(graph.keys()) V = len(vertices) # Initialize distances: source = 0, all others = infinity dist = {v: float('inf') for v in vertices} dist[source] = 0 # Initialize predecessors (for path reconstruction) pred = {v: None for v in vertices} # Build list of all edges edges = [] for u in graph: for v, weight in graph[u]: edges.append((u, v, weight)) # Main loop: relax all edges V-1 times for i in range(V - 1): # Track if any relaxation occurred any_relaxation = False # Relax every edge for u, v, weight in edges: if dist[u] != float('inf') and dist[u] + weight < dist[v]: dist[v] = dist[u] + weight pred[v] = u any_relaxation = True # Early termination: if no relaxation, we're done if not any_relaxation: break # Check for negative cycles (V-th iteration) for u, v, weight in edges: if dist[u] != float('inf') and dist[u] + weight < dist[v]: return None # Negative cycle detected! return dist, predAlgorithm Breakdown:
Initialization (Lines 15-22): Set all distances to infinity except the source (distance 0). Initialize predecessor pointers to null for path reconstruction.
Edge List Construction (Lines 25-28): Collect all edges into a flat list. In an edge list representation, this step is unnecessary—the graph already is the edge list.
Main Loop (Lines 31-43): The algorithm's heart. Iterate V-1 times. In each iteration, attempt to relax every edge. Track whether any relaxation occurred for early termination.
Early Termination (Lines 40-42): If an entire iteration produces no relaxations, all shortest paths have been found. This optimization can dramatically improve performance on sparse graphs or when shortest paths are short.
Negative Cycle Check (Lines 45-48): After V-1 iterations, attempt one more round of relaxation. If any edge can still be relaxed, the graph contains a negative cycle reachable from the source.
The number V-1 isn't arbitrary—it's the precise number of iterations needed to guarantee correctness. Let's understand why rigorously.
The Maximum Path Length Argument:
Consider a graph with V vertices. A simple path (one that doesn't repeat vertices) can visit at most V vertices. Since a path with V vertices has V-1 edges, any simple shortest path has at most V-1 edges.
Why do we care about simple paths?
If the graph has no negative cycles, shortest paths are always simple. Why? Because if a shortest path contained a cycle:
Therefore, without negative cycles, all shortest paths are simple, hence have ≤ V-1 edges.
The Path-Length Invariant (Detailed Proof):
Claim: After iteration k of the main loop, for all vertices v, if the true shortest path from source to v has at most k edges, then dist[v] equals the true shortest path distance.
Proof by Induction:
Base Case (k = 0):
After 0 iterations (just initialization), only dist[source] = 0 is set correctly. The only vertex with a 0-edge shortest path is the source itself (path of length 0 from source to source). ✓
Inductive Step: Assume the claim holds after iteration k. We'll show it holds after iteration k+1.
Consider vertex v whose true shortest path P has exactly k+1 edges:
By the inductive hypothesis, after iteration k, dist[u] is correct (since u's shortest path has k edges or fewer—it's the same path minus the last edge).
During iteration k+1, when we relax edge (u, v):
dist[u] = true shortest distance to udist[v] > dist[u] + w(u, v)?dist[v] = dist[u] + w(u, v)This gives us dist[v] = dist[u] + w(u, v) = (shortest distance to u) + (weight of last edge) = (shortest distance to v using path P).
Since P is the optimal path, dist[v] is now correct. ✓
Conclusion: After V-1 iterations, the claim holds for k = V-1, which covers all possible simple path lengths.
Think of each iteration as 'allowing shortest path information to propagate one hop further.' The source starts with correct distance. Iteration 1 propagates to neighbors. Iteration 2 propagates to neighbors of neighbors. After V-1 iterations, information has propagated along the longest possible simple path.
Why Not Fewer Iterations?
Can we ever need all V-1 iterations? Yes! Consider a pathological graph:
Source → v₁ → v₂ → v₃ → ... → vₙ₋₁
A simple chain of V vertices. The shortest path to vₙ₋₁ has exactly V-1 edges. If we relax edges in the 'wrong' order (from vₙ₋₁ back toward source), each iteration only propagates one hop. We genuinely need all V-1 iterations.
Why Not More Iterations?
If there's no negative cycle, V-1 iterations suffice because any additional iteration would only relax edges where dist[u] is already optimal, leading to no changes. The V-th iteration is only useful for negative cycle detection.
Let's trace through Bellman-Ford on a concrete example with both positive and negative edges.
Graph Structure:
S ----5----> A ----(-2)----> B
| | |
2 3 4
↓ ↓ ↓
C ----6----> D <----(-1)---- E
Edge List: (in arbitrary order)
Vertices: S, A, B, C, D, E (V = 6) Edges: 7 edges (E = 7) Iterations needed: V - 1 = 5
Initialization:
dist = {S: 0, A: ∞, B: ∞, C: ∞, D: ∞, E: ∞}
pred = {S: None, A: None, B: None, C: None, D: None, E: None}
Iteration 1:
Relax each edge:
After Iteration 1:
dist = {S: 0, A: 5, B: 3, C: 2, D: 6, E: 7}
pred = {S: None, A: S, B: A, C: S, D: E, E: B}
Note: Remarkably, in one iteration (with this edge order), all distances got reasonable values! But are they optimal? Let's continue.
Iteration 2:
Relax each edge with current distances:
After Iteration 2:
dist = {S: 0, A: 5, B: 3, C: 2, D: 6, E: 7}
(No changes!)
Early Termination!
Since iteration 2 produced no relaxations, the algorithm can terminate early. All shortest paths have been found.
Final Result:
Notice that the path to B goes through A even though A is 5 units away. The negative edge A → B (-2) makes this worthwhile: 5 + (-2) = 3, which is better than any alternative. The path to D also benefits from the negative edge E → D; without it, D would cost 8 via C.
One of Bellman-Ford's remarkable properties is that the order in which edges are relaxed within each iteration does not affect correctness. The final distances are always correct after V-1 iterations, regardless of edge order.
Why order doesn't matter:
The path-length invariant guarantees that after k iterations, all k-edge shortest paths are correct. This holds regardless of the order edges are processed within each iteration. Intuitively:
What order does affect: Performance
While order doesn't affect correctness, it dramatically affects the number of useful relaxations per iteration:
Best case: Edges processed in topological order (from source outward). Each iteration might make progress on many fronts.
Worst case: Edges processed in reverse topological order. Each iteration only propagates one level of information.
The early termination optimization partially mitigates this—if we're lucky with order, we terminate early.
The SPFA Optimization (Preview):
The Shortest Path Faster Algorithm (SPFA) improves on this by only relaxing edges whose source vertex's distance changed in the previous iteration. This avoids wasted relaxations while maintaining correctness. SPFA uses a queue to track which vertices need their outgoing edges relaxed.
However, SPFA's worst-case complexity is still O(V × E), and pathological graphs can force it to perform as poorly as standard Bellman-Ford. For guaranteed performance on graphs with negative weights, the standard algorithm remains the reliable choice.
When implementing Bellman-Ford, you typically don't worry about edge order—just iterate through your edge list in whatever order it's stored. The early termination check will handle most practical cases efficiently. Only in performance-critical applications with specific graph structures would you consider edge ordering strategies.
Bellman-Ford handles several edge cases gracefully:
Disconnected Vertices:
If a vertex v is not reachable from the source, dist[v] remains infinity forever. No path exists, and no edge relaxation can affect it. This is correct: the shortest path distance to an unreachable vertex is undefined (or infinity, if we treat 'no path' as infinite distance).
Zero-Weight Edges:
Zero-weight edges work perfectly. Relaxation: dist[v] = dist[u] + 0 might or might not improve dist[v], depending on existing estimates. Nothing special is required.
Self-Loops:
An edge from v to v (self-loop) with weight 0 is benign. With positive weight, it never helps (why add cost to return to the same place?). With negative weight, it creates a negative cycle (v → v)— detected by the V-th iteration check.
Parallel Edges:
Multiple edges between the same pair of vertices are handled naturally. When relaxing, we check each edge independently. The one providing the best improvement wins.
Be careful with infinity in implementations! The condition dist[u] != infinity before relaxing prevents issues like infinity + (-5) = very large number (which might appear finite). Always check that the source vertex has a finite distance before attempting relaxation.
Source Vertex Edge Cases:
Distance alone often isn't enough—we need the actual shortest path. The predecessor array enables this.
During Relaxation:
Whenever we update dist[v], we also record pred[v] = u, remembering that the best-known path to v comes through u.
Path Reconstruction Algorithm:
1234567891011121314151617181920212223242526272829303132
def reconstruct_path(pred, source, target): """ Reconstructs the shortest path from source to target. Args: pred: Predecessor dictionary from Bellman-Ford source: Source vertex target: Target vertex Returns: List of vertices forming the path, or None if no path """ if pred[target] is None and target != source: return None # No path exists path = [] current = target while current is not None: path.append(current) current = pred[current] path.reverse() # Path was built backwards return path # Example usage:# result = bellman_ford(graph, 'S')# if result:# dist, pred = result# path = reconstruct_path(pred, 'S', 'D')# print(f"Shortest path: {' -> '.join(path)}")# print(f"Distance: {dist['D']}")Why This Works:
Edge Case: Source Vertex
The source has pred[source] = None, which terminates our backward traversal correctly.
Edge Case: Unreachable Target
If target is unreachable, pred[target] = None but target ≠ source. We detect this and return None.
Path Length Verification:
A valid path from source to target should have exactly as many edges as dist[target] suggests (in terms of weight sum). We can verify by summing edge weights along the reconstructed path.
We've thoroughly examined the core of the Bellman-Ford algorithm:
What's Next:
The next page addresses one of Bellman-Ford's most important capabilities: detecting negative-weight cycles. We'll see how the V-th iteration check works, understand what negative cycles mean semantically, and learn how to identify which vertices are affected by negative cycles.
You now understand the Bellman-Ford algorithm's core mechanism: repeated relaxation over all edges. You can trace the algorithm's execution, understand why V-1 iterations suffice, and reconstruct optimal paths from predecessor pointers. Next, we'll explore negative cycle detection.