Medium Problemsgraphminimization

Floyd Warshall Algorithm

Given a weighted directed graph that may contain negative edge weights but no negative cycle, find the shortest distance between every pair of vertices at once.

Note. Filed under Medium in the course's source list. It is a graph relaxation algorithm rather than textbook tabulation, though allowing one more intermediate vertex per phase is genuinely a DP over 'shortest path using only the first k vertices as intermediates'.

Do this lesson first: coin change

Example input

4 vertices, edges 0→1 (3), 0→2 (8), 1→2 (-2), 1→3 (9), 2→3 (1), 3→0 (2), 3→1 (4)

Expected output

1 → 0 costs 1 (every other pair's cost is in the last row that shows it)

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[k][i][j] is the cost of the cheapest path from i to j whose stops in between all come from the first k vertices, 0 to k - 1. Row 0 allows no stops at all, so it is just the edges. Three numbers name the state, so the table unrolls each layer's matrix into one row: one row per k, one column per ordered pair i → j. The diagonal is left out, since a vertex is 0 away from itself when there is no negative cycle. This is the note's "shortest path using only the first k vertices as intermediates", one layer per phase.

dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][m] + dp[k - 1][m][j]), where m = k - 1 is the vertex newly allowed

Ask whether the cheapest i → j path that may stop at vertices 0 to m actually stops at m. If not, it only uses 0 to m - 1 and is already dp[k - 1][i][j]. If it does, it passes m exactly once, since with no negative cycle going round a loop never helps, and m cuts it into two pieces, i → m and m → j, each stopping only at 0 to m - 1: dp[k - 1][i][m] + dp[k - 1][m][j]. Two candidates, take the smaller. It is the coin-change lesson's minimum over a last decision, with the decision shrunk to yes or no; that lesson derives the pattern and this page assumes it. The second candidate is a PAIR of cells, which is why the compare lights two cells at once.

Row 0 is the edge weights, ∞ where there is no edge. Each row reads only earlier rows, so the table fills one row at a time, which is one phase of the algorithm. A dot is a pair that starts or ends at the vertex m that row adds: dp[k][i][m] = min(dp[k - 1][i][m], dp[k - 1][i][m] + dp[k - 1][m][m]), and dp[k - 1][m][m] = 0 (the diagonal left out of the table), so it cannot change, and the same holds for dp[k][m][j] with the 0 first. The row skips it and anything that needs it reads the last row that shows it, which is where the longer arrows come from. That same fact is why the textbook code can overwrite one matrix in place: during phase m, the row and column of m never move.

Tabulation, phase by phase: n phases over n² pairs, O(n³). The table keeps every phase so you can watch pairs improve, and the dots show that each phase only touches the pairs that avoid its new vertex. The code below keeps a single matrix and updates it in place, which is safe for the reason in the bases: what a phase reads, the row and column of its own vertex, is exactly what it never changes. Every pair is answered in one run, each in the last row that shows it, which is the point of the algorithm over running bellman-ford from every vertex.

Time O(n³)Space O(n³) for the layered table, O(n²) with one matrix updated in place

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 is the edge weights, ∞ where there is no edge. Each row reads only earlier rows, so the table fills one row at a time, which is one phase of the algorithm. A dot is a pair that starts or ends at the vertex m that row adds: dp[k][i][m] = min(dp[k - 1][i][m], dp[k - 1][i][m] + dp[k - 1][m][m]), and dp[k - 1][m][m] = 0 (the diagonal left out of the table), so it cannot change, and the same holds for dp[k][m][j] with the 0 first. The row skips it and anything that needs it reads the last row that shows it, which is where the longer arrows come from. That same fact is why the textbook code can overwrite one matrix in place: during phase m, the row and column of m never move.

Graph

A: all weights positiveB: a negative edge

Edges: 0→1 (3), 0→2 (8), 1→2 (-2), 1→3 (9), 2→3 (1), 3→0 (2), 3→1 (4).

The walkthrough uses this input. Finish it to unlock the others.

Rows ↓
Cols →

0→1

0→2

0→3

1→0

1→2

1→3

2→0

2→1

2→3

3→0

3→1

3→2

none

3

8

∞

-2

9

∞

1

2

4

∞

0

·

-2

9

·

∞

1

·

4

10

0-1

·

1

12

·

∞

·

1

2

·

2

0-2

3

·

2

∞

·

-1

·

2

4

·

0-3

3

1

·

1

-2

·

3

5

·

Rows ↓stops allowed

Cols →pair i → j: cheapest path cost

floyd-warshall.ts

1function floydWarshall(n, edges) {
2 const d = Array.from({ length: n }, (_, i) =>
3 Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
4 for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);
5 for (let m = 0; m < n; m++) { // vertex m may now be a stop
6 for (let i = 0; i < n; i++) {
7 for (let j = 0; j < n; j++) {
8 d[i][j] = Math.min(d[i][j], d[i][m] + d[m][j]);
9 }
10 }
11 }
12 return d;
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

floyd-warshall.ts

1function floydWarshall(n, edges) {
2 const d = Array.from({ length: n }, (_, i) =>
3 Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
4 for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);
5 for (let m = 0; m < n; m++) { // vertex m may now be a stop
6 for (let i = 0; i < n; i++) {
7 for (let j = 0; j < n; j++) {
8 d[i][j] = Math.min(d[i][j], d[i][m] + d[m][j]);
9 }
10 }
11 }
12 return d;
13}

Where people go wrong

Putting the stop loop innermost, for i, for j, for m. It looks like the same three loops, but it settles each pair in a single pass, using whatever the other pairs hold at that moment, so a route that needs two or more stops can be missed. On graph B it answers 11 for 1 → 0 instead of 1: it settles 1 → 0 before it has found 1 → 3 for -1. The stop loop must be outermost, because each phase relies on every pair already being final for the stops before it. The second trap is running it on a graph that does have a negative cycle and trusting the result; check the diagonal afterwards, where a negative d[v][v] means v lies on a negative cycle, and any pair whose route can pass through v has no shortest distance.

Detect a negative cycle.
Keep the diagonal in the matrix and run the same phases. A negative cycle through i makes d[i][i] negative by the end; nothing else in the recurrence changes.
Only ask which pairs can reach each other.
Replace min with OR and + with AND over true/false cells. Same layers, same order, same in-place safety; this is Warshall's transitive closure.
Report the path, not just its cost.
Keep a next-hop matrix and update next[i][j] to next[i][m] whenever the through-m candidate wins. The costs and the order are unchanged.

Bellman–Ford Algorithm Maximum Tip Calculator