Skip to content

Floyd-Warshall

Dijkstra answers "how far is everything from one source?" Floyd-Warshall answers "how far is everything from everything?" Three nested loops, one DP idea, and you get all \(V^2\) pairwise distances. The algorithm is \(O(V^3)\), which is too slow for large graphs but perfect when \(V \leq 500\). Its real power emerges when you understand what each iteration actually computes — that insight unlocks a class of problems no other algorithm handles cleanly.

The DP

Key idea: try routing through vertex k to improve i-to-j distance

Floyd-Warshall distance matrix before and after all intermediate vertices

Define \(\text{dist}_k[i][j]\) as the shortest path from \(i\) to \(j\) using only intermediate nodes from \(\{1, 2, \ldots, k\}\).

Base case: \(\text{dist}_0[i][j]\) = direct edge weight (or \(\infty\) if no edge).

Transition: at pivot \(k\), the shortest path either uses \(k\) as an intermediate or it doesn't.

\[\text{dist}_k[i][j] = \min(\text{dist}_{k-1}[i][j],\ \text{dist}_{k-1}[i][k] + \text{dist}_{k-1}[k][j])\]

We do this in-place — no need to store all \(k\) layers:

const long long INF = 1e18;

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dist[i][k] != INF && dist[k][j] != INF)
                dist[i][j] = min(dist[i][j],
                                 dist[i][k] + dist[k][j]);

Gotcha. The loop order matters. \(k\) must be the outermost loop. If you put \(i\) or \(j\) outermost, the DP recurrence is evaluated in the wrong order and results are incorrect. This is the single most common Floyd-Warshall bug.

Why In-Place Works

You might worry that updating dist[i][k] or dist[k][j] during the \(k\)th iteration corrupts later lookups. It doesn't. When the pivot is \(k\):

  • dist[i][k] = shortest path from \(i\) to \(k\) using intermediates \(\{1, \ldots, k\}\). But \(k\) can't be an intermediate on a path ending at \(k\) (without a cycle), so this equals \(\text{dist}_{k-1}[i][k]\).
  • Same argument for dist[k][j].

The pivot row and column are unchanged by the \(k\)th iteration. In-place is safe.

Full Trace

Graph with 4 nodes:

1 --3-- 2
|       |
7       1
|       |
3 --2-- 4

Edges (undirected): (1,2,3), (1,3,7), (2,4,1), (3,4,2).

Initial dist[][]:

1 2 3 4
1 0 3 7 ∞
2 3 0 ∞ 1
3 7 ∞ 0 2
4 ∞ 1 2 0

Pivot k=1: Route through node 1.

Pair Old Via 1 New
(2,3) ∞ 3+7=10 10
(3,2) ∞ 7+3=10 10

Pivot k=2: Route through node 2.

Pair Old Via 2 New
(1,4) ∞ 3+1=4 4
(4,1) ∞ 1+3=4 4
(3,4) 2 10+1=11 2 (no change)

Pivot k=3: Route through node 3.

Pair Old Via 3 New
(1,4) 4 7+2=9 4 (no change)

No improvements.

Pivot k=4: Route through node 4.

Pair Old Via 4 New
(1,3) 7 4+2=6 6
(3,1) 7 2+4=6 6
(2,3) 10 1+2=3 3
(3,2) 10 2+1=3 3

Final dist[][]:

1 2 3 4
1 0 3 6 4
2 3 0 3 1
3 6 3 0 2
4 4 1 2 0

Verify: shortest \(1 \to 3\) is \(1 \to 2 \to 4 \to 3 = 3 + 1 + 2 = 6\). Correct.

CSES Shortest Routes II

Problem: \(N\) nodes, \(M\) edges, \(Q\) queries. Each query asks for the shortest distance between two nodes. \(N \leq 500\).

Floyd-Warshall's home turf. With \(N \leq 500\), the \(O(N^3) = 1.25 \times 10^8\) operations run comfortably. Handle multiple edges between the same pair by keeping the minimum.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    const long long INF = 1e18;
    vector<vector<long long>> dist(n + 1,
        vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c);
        dist[b][a] = min(dist[b][a], c);
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j],
                                     dist[i][k] + dist[k][j]);

    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (dist[a][b] >= INF ? -1 : dist[a][b]) << "\n";
    }
}

Detecting Negative Cycles

After Floyd-Warshall, check the diagonal. If dist[i][i] < 0, node \(i\) lies on a negative cycle.

for (int i = 1; i <= n; i++)
    if (dist[i][i] < 0)
        // node i is on a negative cycle

Key insight. Floyd-Warshall detects negative cycles for free — just check the diagonal. No extra iteration needed, unlike Bellman-Ford.

What Each Pivot k Computes

This is where Floyd-Warshall becomes more than a shortest-path algorithm. After processing pivot \(k\), dist[i][j] equals the shortest path from \(i\) to \(j\) using only nodes \(\{1, \ldots, k\}\) as intermediates. You can snapshot this state to answer "restricted" queries.

AtCoder abc208_d — Shortest Path Queries 2

Problem: Weighted directed graph, \(N\) nodes. Compute:

\[\sum_{k=1}^{N} \sum_{i=1}^{N} \sum_{j=1}^{N} f_k(i, j)\]

where \(f_k(i, j)\) is the shortest distance from \(i\) to \(j\) using only intermediates \(\{1, \ldots, k\}\), or 0 if no path exists.

This directly exposes Floyd's DP. After each pivot \(k\), sum all finite distances.

long long total = 0;
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dist[i][k] != INF && dist[k][j] != INF)
                dist[i][j] = min(dist[i][j],
                                 dist[i][k] + dist[k][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dist[i][j] != INF)
                total += dist[i][j];
}
cout << total << "\n";

Key insight. Most people treat Floyd-Warshall as a black box. But each pivot produces a meaningful intermediate state. Problems that ask about "restricted intermediates" are exploiting this DP structure directly.

AtCoder abc079_d — Wall

Problem: A grid of digits 0-9. Change every non-1 digit to 1. Changing digit \(c\) to \(d\) costs cost[c][d]. Chaining is allowed: 5→3→1 might be cheaper than 5→1. Minimize total cost.

This is shortest paths on a 10-node graph where nodes are digits and edges are transformation costs. Run Floyd-Warshall on the \(10 \times 10\) matrix. Then for each cell with digit \(c \neq 1\), add dist[c][1].

// Read 10x10 cost matrix into dist[0..9][0..9]
for (int k = 0; k < 10; k++)
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            dist[i][j] = min(dist[i][j],
                             dist[i][k] + dist[k][j]);
// Answer: sum of dist[c][1] for each cell with digit c != 1

\(V = 10\) makes Floyd instant. This pattern — Floyd on a tiny auxiliary graph — shows up more than you'd expect.

Floyd-Warshall vs Running Dijkstra V Times

Graph type Floyd-Warshall V x Dijkstra
Dense (\(E = V^2\)) \(O(V^3)\) \(O(V^3 \log V)\)
Sparse (\(E = V\)) \(O(V^3)\) \(O(V^2 \log V)\)
Negative edges Works Fails
Implementation 5 lines 15+ lines

Rule of thumb: \(V \leq 500\) and you need all pairs? Floyd. \(V > 500\)? You probably can't store the \(V^2\) output anyway.

Exercises

  1. Loop order. Swap the \(k\) and \(i\) loops. Run it on the 4-node example. Which entries end up wrong and why?

  2. Path reconstruction. Track next[i][j] — the first node after \(i\) on the shortest path to \(j\). When dist[i][k] + dist[k][j] improves dist[i][j], set next[i][j] = next[i][k]. How do you reconstruct the full path?

  3. Transitive closure. Replace min with logical OR and weights with booleans. What does the algorithm compute? (Reachability between all pairs — useful for LC 1462.)

Problems

Problem Link Difficulty
CSES — Shortest Routes II cses.fi/problemset/task/1672 Easy
AtCoder abc208_d — Shortest Path Queries 2 atcoder.jp/contests/abc208/tasks/abc208_d Medium
AtCoder abc079_d — Wall atcoder.jp/contests/abc079/tasks/abc079_d Easy
LC 1334 — Find the City leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance Medium
LC 1462 — Course Schedule IV leetcode.com/problems/course-schedule-iv Medium