Bellman-Ford & Floyd-Warshall

Dijkstra's algorithm settles a node once and never looks back, which is only safe when no link subtracts. With negative weights (a refund, a downhill segment, a profit), take the slow, safe road: relax every link, then do it again, until nothing changes.

That is Bellman-Ford. After round r, every node whose shortest route uses at most r links has its final distance. A shortest route never repeats a node, so it has at most n − 1 links, and n − 1 rounds are always enough.

Unless a negative cycle is reachable: a loop whose weights add up to less than zero. Going round it once more always lowers the total, so no shortest route exists at all. Bellman-Ford detects it with one extra pass: if any link can still be relaxed after n − 1 rounds, there is a negative cycle.

Here the links are listed in an unhelpful order, so the first round only gets one link away from the start. Watch the negative link 2 → 3 improve node 3 in round 2, and that improvement reach node 4 in round 3.

Dijkstra's algorithm would settle node 3 at 5, through node 1, before it even took node 2 at 6. The cheaper route 0 → 2 → 3, at 6 − 4 = 2, turns up only after node 3 is settled, too late for the nodes it already reached through node 3.

Because round r covers routes of up to r links, Bellman-Ford can also answer "cheapest with at most k stops": run k + 1 rounds. One detail matters. Within a round, a price set earlier in the same round must not be extended again, or a route could gain two flights at once. So each round reads from a copy of the previous round's prices.

When you need the distance between every pair of nodes, Floyd-Warshall builds an n × n table. It starts with the direct links, then lets each node in turn act as a stop in the middle: for node k, every pair i, j checks whether i → k → j beats the table's current i → j. After every node has had its turn, the table holds every shortest distance.

This is dynamic programming: after round k, each entry is the shortest route that only stops at nodes 0 to k on the way. The order of the loops matters: k must be the outer one.

Negative links are fine here too, and a negative cycle shows up as a negative number on the diagonal: a node that can return to itself for less than nothing.

Floyd-Warshall's three short loops make it the easiest to write when n is small. For every pair in a large sparse graph with no negative weights, running Dijkstra's algorithm from each node is faster.