Bellman-Ford Algorithm Structure
What You'll Learn
You'll understand the two-phase structure of Bellman-Ford: the relaxation loop and the separate negative cycle detection step.
The Two-Phase Architecture
Unlike Dijkstra's algorithm (which you've already learned), Bellman-Ford solves shortest paths even when negative edge weights exist. To do this safely, it uses a clear two-phase structure:
Phase 1: The Relaxation Loop
The first phase runs V-1 iterations (where V is the number of vertices), and in each iteration it attempts to relax every single edge in the graph.
Think of it like this: imagine you're trying to find the cheapest delivery routes in a city. In round 1, you check all roads and update any cheaper routes you find. In round 2, you do the same thing again—because a cheaper route discovered in round 1 might now unlock an even cheaper option elsewhere. You repeat this V-1 times because the longest simple path between any two vertices can have at most V-1 edges.
After V-1 iterations, if no negative cycles exist, you're guaranteed to have found all shortest paths.
Phase 2: Negative Cycle Detection
The second phase runs one more iteration through all edges. If any edge can still be relaxed (meaning we found an even shorter path), that's proof a negative cycle exists—a loop whose total weight is negative, allowing infinite improvement.
This is like discovering a delivery route that somehow gives you money back each time you complete it—clearly something's wrong!
Why This Structure Works
The separation is elegant: Phase 1 assumes everything's normal and finds paths. Phase 2 validates that assumption by checking whether Phase 1 should have finished.
Key Takeaway: Bellman-Ford uses a two-phase structure—V-1 relaxation rounds to find shortest paths, followed by one validation round to detect negative cycles that would make shortest paths undefined.