Floyd Warshall

All-pairs shortest paths: give every vertex a turn as the waypoint

time O(V^3)space O(V^2)

Any shortest path from i to j either never touches vertex k, or it does — and if it does, it is exactly the shortest i-to-k path followed by the shortest k-to-j path, both already known once k has had its turn. So looping k from 0 to n-1 and, for every pair, checking whether routing through k beats the current best, builds the true all-pairs answer in place — no extra storage, no per-source restart. The badge on each vertex below is the current shortest distance in the row being narrated; the highlighted arrows show a two-hop improvement actually just found.

Details

Animated on: 4 vertices, directed weighted edges 0->1(5), 0->3(10), 1->2(3), 2->3(1) — find the shortest distance between every pair of vertices.

Problem:Floyd WarshallMedium

All-pairs shortest paths: give every vertex a turn as the waypoint

step 1 / 11

Row 0 initialized directly from its edges

inf

Before any vertex is allowed as a waypoint, dist[i][j] is just the direct edge weight, 0 on the diagonal, or infinity where no edge exists. Row 0 starts at [0, 5, inf, 10] — only the two edges leaving vertex 0 are known yet.

Pseudocode

1FUNCTION floydWarshall(n, edges):
2  FOR i FROM 0 TO n - 1
3    FOR j FROM 0 TO n - 1
4      dist[i][j] <- INFINITY
5    dist[i][i] <- 0
6  FOR EACH (a, b, w) IN edges
7    dist[a][b] <- w
8  FOR k FROM 0 TO n - 1
9    FOR i FROM 0 TO n - 1
10      FOR j FROM 0 TO n - 1
11        IF dist[i][k] + dist[k][j] < dist[i][j]
12          dist[i][j] <- dist[i][k] + dist[k][j]
13  RETURN dist

← / → step · space play · Home restart

Every step in words

Show all 11 steps

Before any vertex is allowed as a waypoint, dist[i][j] is just the direct edge weight, 0 on the diagonal, or infinity where no edge exists. Row 0 starts at [0, 5, inf, 10] — only the two edges leaving vertex 0 are known yet.
Let every path route through 0 if that helps. Every pair (i, j) gets one chance to improve: dist[i][j] <- MIN(dist[i][j], dist[i][0] + dist[0][j]).
Checked every (i, j) pair with 0 in the middle — nothing beats a distance already recorded, so row 0 stays [0, 5, inf, 10].
Let every path route through 1 if that helps. Every pair (i, j) gets one chance to improve: dist[i][j] <- MIN(dist[i][j], dist[i][1] + dist[1][j]).
0 -> 1 -> 2 costs dist[0][1] + dist[1][2] = 5+3 = 8, beating the previous inf. dist[0][2] <- 8.
Let every path route through 2 if that helps. Every pair (i, j) gets one chance to improve: dist[i][j] <- MIN(dist[i][j], dist[i][2] + dist[2][j]).
Route 0 to 3 via 2: the already-shortest dist[0][2] = 8 (not a single edge — it is itself a path built from an earlier k) plus dist[2][3] = 1 totals 9, beating the previous 10. dist[0][3] <- 9.
1 -> 2 -> 3 costs dist[1][2] + dist[2][3] = 3+1 = 4, beating the previous inf. dist[1][3] <- 4.
Let every path route through 3 if that helps. Every pair (i, j) gets one chance to improve: dist[i][j] <- MIN(dist[i][j], dist[i][3] + dist[3][j]).
Checked every (i, j) pair with 3 in the middle — nothing beats a distance already recorded, so row 0 stays [0, 5, 8, 9].
All 4 vertices have each been tried as the intermediate stop, so every dist[i][j] is final: row 0 = [0, 5, 8, 9], row 1 = [inf, 0, 3, 4], row 2 = [inf, inf, 0, 1], row 3 = [inf, inf, inf, 0]. RETURN dist.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Floyd Warshall in the editor All Graph problems Back to roadmap