Floyd-Warshall

All-pairs shortest paths with a compact dynamic-programming recurrence. · 9 min read

Concept

Floyd-Warshall computes shortest paths between every pair of vertices. Instead of choosing one source, it builds a dist[i][j] table and gradually allows more intermediate vertices on the path.

Interactive visualization: Floyd-Warshall simulation: matrix DP — step through it frame by frame on this page.

The recurrence

Floyd-Warshall transition

dist[i][j] — Best known path from i to j.
allow vertices 0..k as intermediates — Grow the set of allowed middle vertices one at a time.
either path does not use k — Then dist[i][j] stays as it was.
or path uses k — Then it is dist[i][k] + dist[k][j].
take the minimum — The better of those two cases becomes the new answer.

Result: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

C++ sketch

vector<vector<long long>> dist(n, vector<long long>(n, INF));
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (auto [u, v, w] : edges) dist[u][v] = min(dist[u][v], w);

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][k] == INF || dist[k][j] == INF) continue;
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

When to use it

Floyd-Warshall is excellent when V is small to medium and you need many source-target answers. It is especially clean for dense graphs, reachability variants, transitive closure, and graph problems where the all-pairs table becomes a building block.

Complexity and negative cycles

Time is O(V³) because of the three nested loops over k, i, and j. Space is O(V²) for the distance table. After the algorithm, if any dist[i][i] < 0, vertex i can reach a negative cycle.