Floyd-Warshall · All-Pairs Shortest Paths

Shortest distance between every pair of nodes, in one triple loop. The idea: allow paths to route through intermediate node k, one k at a time, and keep the best.

Concept

The DP relation

For every pair (i, j), ask: is going i → k → j shorter than what I have? Formally dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

After processing all k, the matrix holds every shortest distance.

Loop order matters

k (intermediate) is the outermost loop
Then i (row), then j (column)
Row k and column k drive each update
Negative cycle iff any dist[i][i] < 0

Interactive

Route through each k

Row k Column k Cell (i,j) evaluated Improved

Intermediate k = –

slowfast

Step 0

–

Cell (i,j)

–

Updates

Neg cycle?

Implementation

C++

void floydWarshall(vector<vector<int>>& dist) {
    int n = dist.size();
    // dist[i][j] preloaded: edge weight, 0 on diagonal, INF if no edge

    for (int k = 0; k < n; k++)          // intermediate node
        for (int i = 0; i < n; i++)      // source
            for (int j = 0; j < n; j++) {  // destination
                if (dist[i][k] == INF || dist[k][j] == INF) continue;
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];  // relax via k
            }

    // negative cycle if any node reaches itself at a cost < 0
    for (int i = 0; i < n; i++)
        if (dist[i][i] < 0) { /* negative cycle */ }
}

Complexity

Time

O(V³)

Three nested loops over all nodes. Fine for small dense graphs.

Space

O(V²)

The full distance matrix. No extra structures needed.

Gives

all pairs

Every source-destination distance at once, unlike single-source Dijkstra.

Notes

k must be the outer loop. Swap the order and the DP breaks, you'd use paths through k before k is fully processed.
Handles negative edges (unlike Dijkstra). Detects negative cycles via dist[i][i] < 0.
Best when the graph is dense or you genuinely need all pairs. For single-source, Dijkstra/Bellman-Ford win.
Add a next[i][j] matrix to reconstruct the actual paths.
The same triple loop computes transitive closure (reachability) if you swap min-plus for OR-AND.