Recurrence
dᵢⱼ⁽ᵏ⁾ = min(dᵢⱼ⁽ᵏ⁻¹⁾, dᵢₖ⁽ᵏ⁻¹⁾ + dₖⱼ⁽ᵏ⁻¹⁾)
Allow vertex k as an intermediate.
The Floyd–Warshall algorithm finds all-pairs shortest paths with the recurrence , allowing vertex as a possible intermediate stop.
This page is easier if you are comfortable with:
Take three vertices with , and . Allowing vertex 2 as an intermediate: , a shorter route through 2. If instead and the other two are 2 and 3, then . If and the detour costs , then , no change.
Starting from the direct-edge matrix, the algorithm loops , improving every pair ; after the matrix holds the shortest distances. It has three nested loops, so the cost is , the same order as Gaussian elimination (Gaussian elimination cost), whereas running Dijkstra's algorithm from every vertex costs less for sparse graphs (the Dijkstra relaxation step).
It handles negative weights (but not negative cycles). The recurrence is dynamic programming on the set of allowed intermediate vertices. Powers of the adjacency matrix count walks in a similar triple-loop way (walks and the adjacency matrix), and the distances feed bounds for the travelling salesperson problem (travelling salesperson bounds).
Floyd–Warshall improves every pair of distances by allowing one more vertex as a stopover at a time.
The detour 5 + 2 is shorter than the direct edge.
These examples are worked by hand, step by step, so you can compare your own working.
Find for , , .
Find for , , .
Find for , , .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
dᵢⱼ⁽ᵏ⁾ = min(dᵢⱼ⁽ᵏ⁻¹⁾, dᵢₖ⁽ᵏ⁻¹⁾ + dₖⱼ⁽ᵏ⁻¹⁾)
Allow vertex k as an intermediate.
dᵢⱼ = 10, dᵢₖ = 3, dₖⱼ = 4: new dᵢⱼ = 7
Via k is shorter.
dᵢⱼ = 6: stays 6
3 + 4 = 7 > 6.
n³ operations: n = 5 gives 125
Three nested loops.
Floyd–Warshall computes all-pairs shortest paths: after processing vertex k, dᵢⱼ⁽ᵏ⁾ = min(dᵢⱼ⁽ᵏ⁻¹⁾, dᵢₖ⁽ᵏ⁻¹⁾ + dₖⱼ⁽ᵏ⁻¹⁾). It runs in O(n³) time.
dᵢⱼ = 10, dᵢₖ = 3, dₖⱼ = 4. Update dᵢⱼ.
dᵢⱼ = 6, dᵢₖ = 3, dₖⱼ = 4.
How many (i, j, k) triples for n = 5?
dᵢₖ = ∞. What is the new dᵢⱼ if dᵢⱼ = 8?
k innermost ✗
k must be the outer loop ✓
Intermediate vertices accumulate.
dᵢⱼ + dᵢₖ + dₖⱼ ✗
min(dᵢⱼ, dᵢₖ + dₖⱼ) ✓
Take the shorter route.
works with negative cycles ✗
detects them (dᵢᵢ < 0) ✓
Shortest path undefined.
diagonal ∞ ✗
diagonal 0 ✓
Distance to itself.
Try each one on paper, then open the answer. Use the solver above to see the full working.
7
5
64
1000
8
2
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Shortest paths between all pairs.
min(dᵢⱼ, dᵢₖ + dₖⱼ).
O(n³).
The intermediate vertex k.
Dijkstra relaxation.
walks and the adjacency matrix.
More in Discrete maths and number theory and the formula sheets.