Floyd–Warshall Recurrence Explained with Worked Examples

The Floyd–Warshall algorithm finds all-pairs shortest paths with the recurrence , allowing vertex as a possible intermediate stop.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

  • relaxation
  • matrices of distances
  • dynamic programming (idea)

What Floyd–Warshall recurrence means

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).

What is it used for?

Floyd–Warshall improves every pair of distances by allowing one more vertex as a stopover at a time.

How to use floyd–warshall recurrence

  1. Initialise with edge weights ( if no edge, 0 on the diagonal).
  2. For each in turn, update every pair .
  3. Continue until all vertices have been used as intermediates.
  4. Read off the shortest distances.

Graph

Distance d13 before (9) and after (7) allowing vertex 2 as stopoverdirect: 9via 2: 700.511.522.530246810Distance d13 before (9) and after (7) allowing vertex 2 as stopoverstageyGraph with x from 0 to 3 and y from 0 to 10. Shows bars (2); point direct: 9 at (1, 9); point via 2: 7 at (2, 7).

The detour 5 + 2 is shorter than the direct edge.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: via vertex 2

Find for , , .

Worked example
Answer
77
  1. Formula

Example 2: another improvement

Find for , , .

Worked example
Answer
55
  1. Formula

Example 3: no improvement

Find for , , .

Worked example
Answer
66
  1. Formula

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Recurrence

dᵢⱼ⁽ᵏ⁾ = min(dᵢⱼ⁽ᵏ⁻¹⁾, dᵢₖ⁽ᵏ⁻¹⁾ + dₖⱼ⁽ᵏ⁻¹⁾)

Allow vertex k as an intermediate.

Example

dᵢⱼ = 10, dᵢₖ = 3, dₖⱼ = 4: new dᵢⱼ = 7

Via k is shorter.

No improvement

dᵢⱼ = 6: stays 6

3 + 4 = 7 > 6.

Cost

n³ operations: n = 5 gives 125

Three nested loops.

Word problems

Floyd–Warshall computes all-pairs shortest paths: after processing vertex k, dᵢⱼ⁽ᵏ⁾ = min(dᵢⱼ⁽ᵏ⁻¹⁾, dᵢₖ⁽ᵏ⁻¹⁾ + dₖⱼ⁽ᵏ⁻¹⁾). It runs in O(n³) time.

An update

dᵢⱼ = 10, dᵢₖ = 3, dₖⱼ = 4. Update dᵢⱼ.

  1. 3 + 47
  2. Compare7 < 10
  3. Check: 7 ✓7.

No update

dᵢⱼ = 6, dᵢₖ = 3, dₖⱼ = 4.

  1. 7 > 6
  2. Check: stays 6 ✓6.

Cost Higher

How many (i, j, k) triples for n = 5?

  1. 5³
  2. Check: 125 ✓125.

Infinite entries Higher

dᵢₖ = ∞. What is the new dᵢⱼ if dᵢⱼ = 8?

  1. ∞ + anything = ∞
  2. Check: stays 8 ✓8.

Common mistakes

Swapping loop order

k innermost ✗

k must be the outer loop ✓

Intermediate vertices accumulate.

Adding instead of min

dᵢⱼ + dᵢₖ + dₖⱼ ✗

min(dᵢⱼ, dᵢₖ + dₖⱼ) ✓

Take the shorter route.

Negative cycles

works with negative cycles ✗

detects them (dᵢᵢ < 0) ✓

Shortest path undefined.

Forgetting dᵢᵢ = 0

diagonal ∞ ✗

diagonal 0 ✓

Distance to itself.

Exam tips

  1. k outermost.
  2. min(dᵢⱼ, dᵢₖ + dₖⱼ).
  3. O(n³).
  4. Diagonal 0.
  5. Negative cycles: dᵢᵢ < 0.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. min(9, 2 + 5) Foundation

7

2. min(5, 2 + 5) Foundation

5

3. n = 4: n³ Foundation

64

4. n = 10: n³ Higher

1000

5. min(12, 4 + 4) Higher

8

6. min(3, 1 + 1) Higher

2

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Floyd–Warshall
All-pairs shortest paths.
Dynamic programming
Building from subproblems.
Intermediate vertex
A vertex on the path.
Distance matrix
Matrix of dᵢⱼ.
Negative cycle
A cycle of negative total weight.
O(n³)
Cubic running time.

Frequently asked questions

What does Floyd–Warshall compute?

Shortest paths between all pairs.

What is the recurrence?

min(dᵢⱼ, dᵢₖ + dₖⱼ).

What is its time?

O(n³).

Which loop is outermost?

The intermediate vertex k.

Which page covers Dijkstra?

Dijkstra relaxation.

Which page covers walks and adjacency matrices?

walks and the adjacency matrix.

More in Discrete maths and number theory and the formula sheets.