The Floyd–Warshall algorithm
Old road atlases had a table at the back: the distance between every pair of cities. Floyd–Warshall is a way to compute such a table, and it is one of the shortest algorithms ever written: three loops, one comparison, and every shortest distance falls into place.
The idea
Dijkstra's algorithm and Bellman–Ford find the shortest distances from one start. Floyd–Warshall finds them from every node to every other node at once, in a table with a row and a column per node. It starts with what the edges tell directly, and then improves the whole table by allowing more and more nodes as stops on the way.
Step by step
Fill the table: 0 from each node to itself, the edge's length between neighbours, and infinity elsewhere. Then, for each node k, and for every pair i, j: if the distance from i to k plus the distance from k to j is smaller than the distance from i to j, write the smaller number in. That is the whole algorithm. In code it is three loops, with k on the outside.
An example
Take four nodes with the edges A–B of length 3, B–C 1, A–C 5 and C–D 2. The table starts with those, and infinity for A–D and B–D. Round A changes nothing, since every way through A is longer. Round B finds A to C through B: 3 + 1 = 4, shorter than 5. Round C finds A to D through C: 4 + 2 = 6, and B to D: 1 + 2 = 3, both the first ways found. Round D changes nothing. The final table: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.
Why the order of the loops matters
The stop k must be the outer loop. After the round for k, every entry is the shortest distance using only the first k nodes as stops, and the next round builds on that: a best path through the new stop is a best path to it plus a best path from it, both already right. Putting k in an inner loop breaks that guarantee and can leave wrong distances. Updating the table in place during a round is safe, because the row and column of k itself do not change in that round.
History and uses
Bernard Roy described the method in 1959. In 1962 Stephen Warshall published it for transitive closure, which asks only whether one node can reach another, and Robert Floyd published it for shortest paths. It computes distance tables and routing tables, finds the diameter of a network, tells which nodes can reach which, and with a negative entry on the diagonal reveals a negative cycle.
Explore it
Open the app and press Step. The graph is on one side and the table on the other. Each round highlights the current stop's row and column; each step writes one pair's shorter distance and outlines the two entries that were added. Cells that changed in this round are tinted. Pick a start and a goal to see the shortest path between them when the table is complete.
Frequently asked questions
What is the time complexity of Floyd–Warshall?
O(n³) for n nodes, whatever the number of edges, and O(n²) memory for the table. It is the method of choice for small or dense graphs, where its simple loop runs very fast.
Floyd–Warshall or Dijkstra from every node?
For a dense graph, or when edges can be negative, Floyd–Warshall is simpler and about as fast. For a large sparse graph with non-negative edges, running Dijkstra's algorithm from each node is faster.
Is Floyd–Warshall dynamic programming?
Yes. It solves the problem for paths with stops among the first k nodes using the answers for the first k − 1 nodes, and keeps only one table, overwriting it as it goes.
What is transitive closure?
The table of which nodes can reach which, ignoring distances. Warshall's version of the algorithm computes it with "or" and "and" instead of "min" and "+".
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try Floyd–Warshall