The Floyd-Warshall algorithm, explained

Dijkstra and Bellman-Ford give distances from one starting node. Floyd-Warshall answers a bigger question: what is the shortest distance between every pair of nodes?

It builds a table of distances and improves it by asking, for each node in turn, whether going through that node makes any pair of nodes closer.

How it works

• Start a table with the direct edge weights, 0 for a node to itself, and infinity where there is no edge.
• Pick one node as a possible stop-over.
• For every pair of nodes, check if going through the stop-over is shorter than the current distance. If so, update the table.
• Repeat with every node as the stop-over.

A small example

Take these directed edges:

A>B:3  B>C:1  A>C:7  C>A:2

A to C: 4 (through B)     C to B: 5 (through A)
B to A: 3 (through C)     C to A: 2

The direct edge A to C costs 7, but going through B costs only 3 + 1 = 4.

What to know about its cost

• O(V³) time.
• Uses O(V²) space for the table.
• Works with any weights and detects negative cycles.

Where it works well

• One run gives all pairs of distances.
• Very short and simple to write.

Where it struggles

• Too slow for large graphs.
• Uses a lot of memory for big tables.

Try it yourself

Open the Graph Algorithms experiment, enter these edges (A>B:3, B>C:1, A>C:7, C>A:2), choose Floyd-Warshall, and step through it. Then try a different graph and watch how the result changes.

Open the Graph Algorithms experiment