Graphs 0/61

Dijkstra and shortest paths · 3 of 4

Bellman-Ford

Find distances when weights can be negative by relaxing every edge in rounds, detect a negative cycle, and limit the number of edges on a path.

2,378 words · 11 min read

Part 1 of 6 Negative weights

Graphs with negative weights

A weight does not have to be a time or a price. In a game it can be the change in a score when we walk through a tunnel, and that change can be negative. Dijkstra's algorithm must not be used on such a graph: one road of negative weight on the courier map was enough to make it give a wrong distance.

The courier map with a negative road

Here is that map again, with the two extra roads 0 → 4 of weight 6 and 4 → 1 of weight −4-4:

412156−401234

The algorithm of the first page, which relaxes every edge in rounds until a round changes nothing, makes no assumption about the weights. It never treats a distance as final before the end, so a negative weight cannot arrive too late for it. That algorithm is Bellman-Ford. On this map, with the roads in the order 0 → 1, 0 → 2, 2 → 1, 1 → 3, 2 → 3, 0 → 4, 4 → 1, it runs like this:

The array dist after each round. The highlighted entries changed in that round.

In round 1 town 1 is first given 4 and then lowered to 3 by 2 → 1, and 1 → 3 gives town 3 the distance 3+1=43 + 1 = 4. At the end of the round 0 → 4 gives town 4 the distance 6, and the negative road lowers town 1 to 6−4=26 - 4 = 2. Round 2 relaxes 1 → 3 again and brings town 3 to 2+1=32 + 1 = 3, the distance that Dijkstra's algorithm missed. Round 3 changes nothing.