Dynamic programming over intermediates
Floyd Warshall computes the shortest path between every pair of nodes using a simple triple loop. The key insight is to allow paths to use a growing set of intermediate nodes.
The relaxation
Process the nodes one at a time as candidate intermediates. For each pair of source and target, ask whether routing through the current intermediate gives a shorter distance than the best known so far. If so, update it.
- Outer loop: the intermediate node allowed.
- Inner loops: every source and target pair.
- Update when going through the intermediate is shorter.
The order matters: the intermediate loop must be outermost, because each stage builds on shortest paths that may use all previously considered intermediates.
Negative cycles
A negative cycle reveals itself when a node's distance to itself becomes negative after the loops finish.
Key idea
Floyd Warshall lets each node in turn act as an intermediate and relaxes every pair through it, computing all pairs shortest paths with a compact triple loop where the intermediate must be the outer loop.