---
title: "Floyd–Warshall"
summary: Three nested loops, every pair of vertices, and a dozen problems that are "Floyd, but the operation is not min".
difficulty: core
tags: [all-pairs, DP, matrix]
time: n^3
space: n^2
prereq: [foundations/representation]
see: [matrices/adjacency, shortest/sparse-tricks]
---

:::definition label="The invariant, which is the whole algorithm"
After the outer loop has reached $k$, $d[i][j]$ is the shortest distance from $i$ to $j$ using only intermediate vertices from $\{0, \dots, k-1\}$.
:::

```cpp floyd-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 \leadsto 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. ∎
:::

:::note title="Why 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
:::props title="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^3/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 \le c$ and, before each stage, check `min over i<j<c of d[i][j] + w(i,c) + w(c,j)` — $O(n^3)$ 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.
:::

```cpp floyd-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];
```

:::example title="Floyd as a semiring"
Every row above is the same program with $(\min, +)$ replaced by another closed semiring: $(\text{or}, \text{and})$ for reachability, $(\max, \min)$ for capacity, $(\min, \max)$ for the bottleneck, matrix multiplication over $(+,\times)$ for walk counting (@matrices/walks-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 \ge 1000$: $10^9$ operations, too slow; run Dijkstra per source if the graph is sparse (@shortest/dijkstra) or Johnson (@shortest/sparse-tricks),
- memory $n^2$: $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^3)$.

:::problems
- [[CSES 1672]] Shortest Routes II | https://cses.fi/problemset/task/1672 | easy | straight Floyd
- [[CSES 1705]] Forbidden Cities | https://cses.fi/problemset/task/1705 | hard | closure + SCC
- [[CF 601A]] The Two Routes | https://codeforces.com/problemset/problem/601/A | core | Floyd on the complement
:::