Dijkstra and Bellman–Ford find distances from one start node. To get the distance between every pair, such as a table of travel times between all cities, you could run one of them from each node. Floyd–Warshall does it with three nested loops and a table, and it is a neat example of dynamic programming.
Number the nodes. Before round 1, a path may not pass through any other node, so the table holds only direct edges. In round k, paths may also pass through node k. For every pair i → j, there are only two possibilities: the best path doesn't use k (keep the old value), or it goes i → k → j, each half using only the earlier nodes, which the table already holds:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
After the round for the last node, any node may be used, so the table holds every shortest distance. Row k and column k never change in round k: going through k to reach k gains nothing.
Row = from, column = to. In round k, k's row and column are shaded green; the cell being updated is outlined in yellow, and the two cells it adds up are blue. Rounds go through the nodes alphabetically, and a distance only changes when the new path is strictly shorter. Only pairs where i can reach k and k can reach j are checked, since the others can't change.
| Floyd–Warshall | |
|---|---|
| Time | O(V³): V rounds, each over all V² pairs |
| Space | O(V²), updating one table in place |
| Negative edges | Fine. A negative cycle shows up as a negative number on the diagonal. |
| When to use | Dense graphs, or when you need all pairs and V is in the hundreds, not millions. |