- Current stop
- Already a stop
- Pair made shorter
- Path
Floyd–Warshall algorithm
How far is it from every town to every other town? Floyd–Warshall answers that in one go, with a table and three nested loops. Each round allows one more node as a stop on the way and asks, for every pair, whether the detour through it is shorter. Step through to see the table fill in and the distances drop. Press Play to watch the table fill in, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. The table holds the shortest distance found so far between every pair of nodes; the number on each edge is its length. Each round allows one more node as a stop on the way, and each step shows a pair that gets shorter through it. Click a node to make it the start; switch the click to Goal and click another node to see the shortest path between them at the end. New graph makes another graph; choose how many nodes and edges it has. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Watch the table: the current stop's row and column are tinted, and each step writes a shorter distance.
- Pick a start and a goal to see the shortest path between them at the end. New graph makes another graph to try.
How Floyd–Warshall works
Make a table with one row and one column per node. Fill in 0 on the diagonal, the edge's length where two nodes are joined, and infinity everywhere else. Then take each node k in turn as a possible stop. For every pair i, j, compare the table's distance from i to j with the distance from i to k plus the distance from k to j, and keep the smaller. After the last node, every entry is the shortest distance between its two nodes.
Why it works
After the round for k, the table holds, for every pair, the shortest path whose stops are all among the nodes handled so far. The round for the next node only has to decide whether that node helps: a shortest path through it is a shortest path to it plus a shortest path from it, both already in the table. This way of building a big answer from smaller ones already found is called dynamic programming. With negative edges it still works, and a negative number on the diagonal reveals a negative cycle.
Frequently asked questions
What is the Floyd–Warshall algorithm?
An algorithm that finds the shortest distance between every pair of nodes in a weighted graph. It keeps a table of distances and, for each node in turn, checks whether going through that node makes any pair shorter.
How fast is Floyd–Warshall?
It has three nested loops over the n nodes, so the work grows with n³, and the table needs n² entries. That is fine for graphs of a few hundred nodes. For large sparse graphs, running Dijkstra's algorithm from every node is faster.
Can Floyd–Warshall handle negative edges?
Yes, as long as there is no negative cycle. If there is one, some entry on the diagonal becomes negative, which is how Floyd–Warshall detects it.
How do I get the paths, not just the distances?
Keep a second table with the next node on the way from i to j. Whenever a pair gets shorter through k, copy the next node from i towards k. Following that table from i to j spells out the path.
Is my graph sent anywhere?
No. The graph is made and the table is filled in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor