Floyd–Warshall: DP on Graphs

A routing table needs the distance between every pair of routers, not just from one source. Floyd–Warshall computes all of them with three nested loops and five lines of code, and it is the cleanest example of DP on a graph.

advanced⏱ 12 min read

←Builds on

10DP Fundamentals: Memo & TableThe state is "shortest path using only the first k vertices", a textbook DP.8Dijkstra's AlgorithmIt answers all pairs at once where Dijkstra answers one source.8Bellman–Ford & Negative EdgesLike Bellman–Ford it relaxes edges repeatedly and copes with negative weights.

Leads to→

10Bitmask DPThe salesman needs distances between every pair of cities, which Floyd–Warshall provides.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01All pairs at once

Dijkstra gives distances from one source. For all pairs you could run it V times, but that fails with negative edges, and Bellman–Ford V times costs O(V²E).

Floyd–Warshall works on a distance matrix d[i][j]: start with the edge weight where an edge exists, 0 on the diagonal, ∞ elsewhere. When it finishes, d[i][j] is the shortest distance from i to j for every pair. It handles negative edges, as long as there is no negative cycle (then “shortest” is meaningless).

In the example graph two edges are negative. The cheapest way from 1 to 2 is not a direct edge at all: 1 → 3 → 4 → 2 costs −2 + 2 − 1 = −1. Finding such routes for all 16 pairs is the job.

02The DP state: which vertices may be used in between

The clever part is the state. Number the vertices 1..V and define

d_k[i][j] = the shortest path from i to j whose intermediate vertices all lie in {1, …, k}.

For k = 0 no intermediates are allowed, so d₀ is the edge matrix. Going from k−1 to k, the shortest path either does not use vertex k (then it is d_{k−1}[i][j]) or uses it exactly once, splitting into i → k and k → j, both with intermediates in {1, …, k−1}:

d_k[i][j] = min(d_{k−1}[i][j], d_{k−1}[i][k] + d_{k−1}[k][j])

After k = V every vertex is allowed, so d_V holds the true distances. There are V layers of V² cells, each O(1), so the total is O(V³).

03Five lines, one rule about loop order

In code you do not need V matrices. Update one matrix in place:

for k: for i: for j: d[i][j] = min(d[i][j], d[i][k] + d[k][j])

This is safe because during round k the values d[i][k] and d[k][j] do not change (going through k to reach k cannot help).

The one rule: k must be the outermost loop. It is the DP layer; i and j are just the cells of that layer. Putting k inside gives wrong answers on some graphs, a classic bug.

Two bonuses. Store next[i][j] when an update happens to rebuild paths. And after the loops, any d[i][i] < 0 reveals a negative cycle through i. With O(V³) time and O(V²) memory, Floyd–Warshall is the right tool for V up to about 400–500, dense graphs, or when you truly need every pair.

Green cells were improved by routing through an intermediate vertex.

Cost at a glance

All-pairs shortest pathsO(V³)

Memory (one matrix)O(V²)

Negative cycle checkO(V)

Remember

The state d_k[i][j] allows only vertices 1..k in between; adding vertex k either helps via i → k → j or does not.
Keep k as the outermost loop; one matrix updated in place is enough.
It works with negative edges, and a negative diagonal entry afterwards signals a negative cycle.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Each phase unlocks one more intermediate vertex k; watch which matrix cells drop and check them against routes through k in the graph.

Interactive visualizerfocus here, then space ← →

Directed graph · intermediate vertices ≤ 0

Shortest distance matrix

i\\j	1	2	3	4
1	0	∞	-2	∞
2	4	0	3	∞
3	∞	∞	0	2
4	∞	-1	∞	0

Floyd–Warshall computes shortest paths between ALL pairs at once. Start with direct edges only; ∞ means “no path yet”.

Pseudocode

 1 d[i][j] = edge weight, ∞ if none, 0 on the diagonal 2 for k in 1..V:   // allow k as an intermediate vertex 3   for all i,j: d[i][j] = min(d[i][j], d[i][k] + d[k][j]) 4 // d now holds all-pairs shortest paths

1 / 1

Check

Three questions. Pick an answer to see why.

Why must k be the outer loop?

After running Floyd–Warshall, d[3][3] = −2. What does it mean?

V = 2000 vertices, E = 5000 non-negative edges, and you need all pairs. Better choice?

Practice

Real problems to lock it in, easiest first.

LeetCodeNetwork Delay Time intermediate↗CSESShortest Routes II intermediate↗LeetCodeFind the City With the Smallest Number of Neighbors at a Threshold Distance intermediate↗LeetCodeCourse Schedule IV intermediate↗