Chapter 6 · Shortest Paths

Floyd–Warshall

Three nested loops, every pair of vertices, and a dozen problems that are "Floyd, but the operation is not min".

core
time n^3
space n^2
2 snippets
all-pairs
DP
matrix

Read first

Definition

After the outer loop has reached k, d[i][j] is the shortest distance from i to j using only intermediate vertices from {0, …, k-1}.

cppfloyd-warshall.cpp

vector<vector<ll>> d(n, vector<ll>(n, INF));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (auto [u, v, w] : edges) {
    d[u][v] = min(d[u][v], (ll)w);
    d[v][u] = min(d[v][u], (ll)w);      // delete for digraphs; keep min() for parallel edges
}
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++) if (d[i][k] < INF)
        for (int j = 0; j < n; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

Proof

Consider a shortest walk i ⇝ j whose intermediates lie in {0..k}. Either it avoids k — then d^(k)[i][j] = d^(k-1)[i][j] — or it passes through k, and the two halves use only {0..k-1} (no negative cycle ⇒ the walk can be taken simple, so k appears once). That is precisely the update d^(k-1)[i][k] + d^(k-1)[k][j]. Induction over k, and k = n allows every vertex. ∎

NoteWhy the loops must be in that order

k is the stage index, so it belongs outermost. Putting k inside is a different (wrong) algorithm: one pass of "i,j outer, k inner" only discovers paths whose intermediates appear in increasing index order. The invariant above is the only thing separating a correct 6-line solution from a wrong one, so state it in a comment in your template.

#What you get for the same cost

Six uses of the same three loops

negative cycle detection: after the algorithm, any d[i][i] < 0 means a negative cycle through i — O(n) extra, no parent chasing,
transitive closure of a digraph: replace (min, +) by (or, and): d[i][j] |= d[i][k] & d[k][j], with a bitset row this is O(n³/64),
widest/bottleneck path: d[i][j] = max(d[i][j], min(d[i][k], d[k][j])),
girth (shortest cycle): run Floyd only for k ≤ c and, before each stage, check min over i<j<c of d[i][j] + w(i,c) + w(c,j) — O(n³) total,
minimax / "minimise the maximum edge on the path": d[i][j] = min(d[i][j], max(d[i][k], d[k][j])),
recover the path: keep nxt[i][j] and update it exactly where you update d — 2 extra lines, and it beats running n Dijkstras when you need all pairs anyway.

cppfloyd-reconstruct.cpp

vector<vector<int>> nxt(n, vector<int>(n, -1));
for (auto [u, v, w] : edges) d[u][v] = min(d[u][v], w), nxt[u][v] = v;
// inside the k-loop, when you improve:
if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; nxt[i][j] = nxt[i][k]; }
// walk: v = i; while (v != j) v = nxt[v][j];

ExampleFloyd as a semiring

Every row above is the same program with (min, +) replaced by another closed semiring: (or, and) for reachability, (max, min) for capacity, (min, max) for the bottleneck, matrix multiplication over (+,×) for walk counting (Counting Walks with Matrix Powers). Recognising "this is Floyd over a different semiring" collapses several problem types into one loop you already have memorised.

#When not to use it

n ≥ 1000: 10⁹ operations, too slow; run Dijkstra per source if the graph is sparse (Dijkstra's Algorithm) or Johnson (0-1 BFS, Dial, Potentials, Johnson),
memory n²: n = 2000 with long long is 32 MB — fine; n = 5000 is 200 MB — not,
if you only need one source, O(nm) BFS/Dijkstra always beats O(n³).

Problems for this page

CSES 1672Shortest Routes IIwarm-upstraight Floyd CSES 1705Forbidden Citieshardclosure + SCC CF 601AThe Two RoutescoreFloyd on the complement