Course contentsShow
← Computer Science
Lesson 981 of 2,87223. Shortest Path AlgorithmsFree lesson

Bellman-Ford Algorithm Structure

The two-phase structure: relaxation loop and negative cycle detection.

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.