Floyd-Warshall Algorithm

July 2026 · 25 min read

The Floyd-Warshall algorithm computes the shortest paths between every pair of vertices in a weighted graph — a problem known as All-Pairs Shortest Paths (APSP). It is one of the most elegant applications of dynamic programming in graph theory: just three nested loops and a single relaxation step. In this post we dissect the DP recurrence, walk through a full 5-node example showing the distance matrix evolve at each iteration, build path reconstruction with a next[][] array, explore negative-cycle detection and transitive closure, and provide an interactive animation you can step through at your own pace.

Why Floyd-Warshall?

Single-source algorithms like Dijkstra and Bellman-Ford answer “what is the shortest path from one source to all other vertices?” But many problems require shortest paths between every pair:

• Network routing: Pre-compute all-pairs distances so any query “shortest path from A to B” is answered in O(1).
• Transitive closure: Determine which vertices can reach which — Floyd-Warshall generalises to boolean reachability.
• Detecting negative cycles: If any diagonal element dist[i][i] becomes negative, there is a negative-weight cycle through vertex i.
• Dense graphs: On dense graphs (E ≈ V²), running Dijkstra V times costs O(V³) anyway, and Floyd-Warshall’s constant factor is much smaller due to cache-friendly matrix access.
• Small vertex count: With V ≤ 400–500, Floyd-Warshall’s O(V³) is perfectly fast and trivially simple to implement.

The DP Recurrence

Let dist(k)[i][j] denote the shortest path from i to j using only vertices {0, 1, …, k} as intermediate nodes. The base case is direct edge weights:

After processing all k from 0 to V−1, dist(V−1)[i][j] holds the true shortest path from i to j (considering all possible intermediates).

Why k Must Be the Outer Loop

The recurrence builds on dist(k−1) values. If k were an inner loop, we would attempt to use intermediate vertex k before computing all (k−1)-optimal paths. The outer k loop ensures that when we process intermediate vertex k, all paths using intermediates {0, …, k−1} are already finalised. This ordering is what makes the DP correct.

In practice, we update the matrix in-place because the values dist[i][k] and dist[k][j] are never worsened by the relaxation step for intermediate k (a shortest path from i to k doesn’t benefit from routing through k again).

Step-by-Step Walkthrough

Let’s trace Floyd-Warshall on this 5-node directed, weighted graph. We will watch the distance matrix evolve as k goes from 0 to 4.

Edges: 0→1 (4), 0→4 (8), 1→2 (2), 1→3 (5), 2→3 (1), 3→4 (3), 4→2 (6).

Notice how each k iteration can use improvements discovered in earlier k iterations. For example, at k=2 we used dist[0][2]=6, which was itself computed at k=1. This cascading improvement is the power of Floyd-Warshall’s DP.

Path Reconstruction

The distance matrix tells us the cost of shortest paths, but not the actual paths. To reconstruct paths, maintain a next[i][j] matrix: next[i][j] stores the first vertex after i on the shortest path from i to j.

Reconstructing a Path

To print the shortest path from u to v, follow the next pointers:

Example: Shortest path from 1 to 4 (cost 6). Starting at next[1][4] = 2, then next[2][4] = 3, then next[3][4] = 4. Path: 1 → 2 → 3 → 4 with total weight 2+1+3 = 6. ✔

Interactive Animation

Step through the Floyd-Warshall algorithm on our 5-node graph. Watch the distance matrix update as each intermediate vertex k is processed. Orange cells show values that improved in the current step.

Detecting Negative Cycles

Floyd-Warshall handles negative edge weights correctly as long as no negative-weight cycle exists. But how do we detect one?

If a negative cycle is detected, the distances in the matrix are unreliable for vertices that can reach or be reached by the cycle. In competitive programming, you may need a second pass to mark all pairs (i,j) where the path passes through a negative cycle as having distance −∞: if dist[i][k] + dist[k][j] < dist[i][j] and dist[k][k] < 0, set dist[i][j] = −∞.

Transitive Closure (Warshall’s Algorithm)

A beautiful special case: replace arithmetic with boolean logic. Instead of “shortest distance,” we ask “can vertex i reach vertex j?” This is the transitive closure of the graph, and the algorithm is called Warshall’s algorithm (1962, the predecessor of Floyd-Warshall).

The logic is identical to Floyd-Warshall: “can i reach j either directly or by going through k?” This is O(V³) but can be optimised with bitset operations to O(V³/64).

C++ Implementation

1. Basic Floyd-Warshall

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

const long long INF = 1e18;

void floydWarshall(vector<vector<long long>>& dist) {
    int V = dist.size();
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j],
                                     dist[i][k] + dist[k][j]);
}

int main() {
    int V = 5;
    vector<vector<long long>> dist(V, vector<long long>(V, INF));
    for (int i = 0; i < V; i++) dist[i][i] = 0;

    // Edges: u, v, weight
    dist[0][1] = 4; dist[0][4] = 8;
    dist[1][2] = 2; dist[1][3] = 5;
    dist[2][3] = 1; dist[3][4] = 3;
    dist[4][2] = 6;

    floydWarshall(dist);

    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++)
            cout << (dist[i][j] >= INF ? -1 : dist[i][j]) << "\t";
        cout << "\n";
    }
    return 0;
}

2. With Path Reconstruction

void floydWarshallPath(vector<vector<long long>>& dist,
                        vector<vector<int>>& nxt) {
    int V = dist.size();
    // Initialise next: nxt[i][j] = j if edge exists
    nxt.assign(V, vector<int>(V, -1));
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            if (dist[i][j] < INF && i != j)
                nxt[i][j] = j;

    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] < INF && dist[k][j] < INF
                    && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    nxt[i][j] = nxt[i][k];
                }
}

vector<int> getPath(int u, int v, vector<vector<int>>& nxt) {
    if (nxt[u][v] == -1) return {};  // no path
    vector<int> path = {u};
    while (u != v) {
        u = nxt[u][v];
        path.push_back(u);
    }
    return path;
}

3. Transitive Closure (Bitset-Optimised)

// O(V^3 / 64) with bitset optimisation
const int MAXV = 500;
bitset<MAXV> reach[MAXV];

void transitiveClosure(int V, vector<pair<int,int>>& edges) {
    for (int i = 0; i < V; i++) {
        reach[i].reset();
        reach[i].set(i);  // i reaches itself
    }
    for (auto& [u, v] : edges)
        reach[u].set(v);

    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            if (reach[i].test(k))
                reach[i] |= reach[k];
    // reach[i].test(j) == true means i can reach j
}

The bitset trick replaces the inner j-loop with a single bitwise OR operation, giving a 64× speedup in practice.

Complexity Analysis

Comparison with repeated Dijkstra: Running Dijkstra from every vertex costs O(V · (V+E) log V) with a binary heap. For dense graphs (E ≈ V²), this is O(V³ log V), worse than Floyd-Warshall. For sparse graphs (E ≈ V), repeated Dijkstra is O(V² log V), much better. Floyd-Warshall wins on simplicity and cache performance for small V.

Competitive Programming Patterns

1. Shortest Paths in Small Graphs

The most common pattern: V ≤ 400, all-pairs shortest paths needed. Build the adjacency matrix, run Floyd-Warshall, answer queries in O(1). Often disguised as “find the city with fewest reachable neighbours within distance threshold” (LeetCode 1334).

2. Minimax Paths

Find the path from i to j that minimises the maximum edge weight along the path. Replace the relaxation with:
dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j])).

3. Widest (Bottleneck) Paths

Find the path that maximises the minimum edge weight (widest bottleneck). Replace with:
dist[i][j] = max(dist[i][j], min(dist[i][k], dist[k][j])).

4. Incremental Vertex Addition

In problems like Codeforces 295B — Greg and Graph, vertices are added one by one. After adding vertex k, run just the k-th iteration of Floyd-Warshall (the outer loop for that single k). This updates all-pairs distances incrementally in O(V²) per vertex addition.

5. Detecting Negative Arbitrage Cycles

Model currency exchange rates as edge weights (use −log(rate) to convert multiplication to addition). Run Floyd-Warshall and check if any dist[i][i] < 0, indicating an arbitrage opportunity.

Practice Problems

Test your understanding with these problems, ordered by difficulty:

Summary

1. Floyd-Warshall solves all-pairs shortest paths in O(V³) time and O(V²) space via DP. The k-loop must be outermost for correctness.
2. The recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) considers all possible intermediate vertices.
3. Path reconstruction uses a next[i][j] matrix updated alongside dist. Follow next pointers to recover the actual path.
4. Negative cycles are detected by checking the diagonal: dist[i][i] < 0 means vertex i is on a negative cycle.
5. Warshall’s algorithm (boolean variant) computes transitive closure with the same structure, optimisable to O(V³/64) using bitsets.
6. Use Floyd-Warshall when V ≤ 500 and you need all-pairs distances. For larger or sparser graphs, prefer repeated Dijkstra or Johnson’s algorithm.
7. In competitive programming, the same framework supports minimax paths, widest paths, and incremental vertex addition.