Bellman-Ford: Relaxing Every Edge V − 1 Times

A shortest path has at most V − 1 edges, and each pass over every edge fixes at least one more of them.

Bellman-Ford finds the shortest paths from one source even when some weights are negative, and reports a negative cycle when there is one. It does not choose which vertex to work on; it relaxes every edge, in any order, V − 1 times, where V is the number of vertices. This card shows why that many passes is enough, why fewer may not be, and how one more pass finds a negative cycle.

A shortest path never repeats a vertex when there is no negative cycle, so it has at most V − 1 edges. After the first pass, every shortest path of one edge has its right distance; after the second, every one of two edges, because its last edge is relaxed from a vertex already right. After V − 1 passes every shortest path is covered.

The trace below runs it on the topic's graph from A with the edges taken in reverse order, from a run. Five vertices means four passes, then a check.

Bellman-Ford's distances after each pass over the topic's graph, edges in reverse order

InputEdges A->B 2, A->C 7, B->C 3, B->D 8, C->D 2, C->E 6 and D->E 1, from A

Start
1. A:0
2. B:∞
3. C:∞
4. D:∞
5. E:∞
A starts at 0 and every other vertex at ∞. The edges are taken in reverse order: D->E, C->E, C->D, B->D, B->C, A->C, A->B.
Pass 1
1. A:0
2. B:2
3. C:7
4. D:∞
5. E:∞
Pass 1. The edges out of C, D and E come first, while their tails are still ∞, so they do nothing. Only A->C and A->B, last in the order, set C to 7 and B to 2.
Pass 2
1. A:0
2. B:2
3. C:5
4. D:9
5. E:13
Pass 2. C->E sets E to 13 and C->D sets D to 9; B->D's 10 does not beat 9. B->C then lowers C to 5, too late for the edges out of C in this pass.
Pass 3
1. A:0
2. B:2
3. C:5
4. D:7
5. E:10
Pass 3. D->E lowers E to 10, and C->D, now from C at 5, lowers D to 7.
Pass 4
1. A:0
2. B:2
3. C:5
4. D:7
5. E:8
Pass 4. D->E, from D at 7, lowers E to 8. This is the fourth pass and V − 1 = 4, so the distances are final.
Check
1. A:0
2. B:2
3. C:5
4. D:7
5. E:8
The check pass over every edge lowers nothing, so the graph has no negative cycle. The distances are A 0, B 2, C 5, D 7 and E 8.

ResultA 0, B 2, C 5, D 7, E 8 after four passes; the check lowers nothing

In reverse order the distances crawl forwards one edge per pass, because each pass reaches an edge before the edge that sets its tail. The run also took the edges in listing order, A->B first, and the first pass set every distance to its final value; the second changed nothing. So one pass can be enough, but only by luck of the order, and V − 1 is what the algorithm can promise for any order. A program that stops after one pass is right on some inputs and wrong on others.

An early stop is safe in the other direction: when a whole pass changes nothing, no later pass can, so the program may finish there.

If the distances are final after V − 1 passes, one more pass can lower nothing. So when a pass after the last one still lowers a distance, some path keeps getting shorter as it gets longer, which only a negative cycle allows. The run added an edge E->C of weight −6, making the cycle C->D->E->C add up to −3, and after four passes the check could still lower D's distance.

Reach for Bellman-Ford when weights can be negative, such as rebates or gains, or when the question is whether a negative cycle exists at all: in currency exchange, with each rate weighted by its negative logarithm, a negative cycle is a loop of trades that makes money.

Bellman-Ford on V vertices and E edges

Time: O(V · E); V − 1 passes over every edge, plus the check
Extra space: O(V); one distance and one parent per vertex
Works on: Negative weights allowed; and reports a negative cycle reachable from the source

On the Algorithms: Graph Algorithms cheatsheet

← → move through sections and cards