Floyd-Warshall Algorithm

Every shortest-path algorithm you’ve seen so far answers a single question: “What’s the shortest path from source S to destination D?” Floyd-Warshall answers a different, bigger question: “What’s the shortest path between every pair of vertices?”

This all-pairs perspective is expensive — O(V³) — but the algorithm is extraordinarily concise. Three nested loops. One recurrence relation. No priority queue, no relaxation step, no graph traversal. Pure dynamic programming.

The Problem

Given a weighted directed graph with V vertices (possibly with negative edge weights but no negative cycles), compute the shortest distance between every pair of vertices (i, j).

Output: a V × V distance matrix where dist[i][j] is the weight of the shortest path from vertex i to vertex j.

The DP Formulation

Define dp[k][i][j] as the shortest path from vertex i to vertex j, using only vertices {0, 1, …, k} as possible intermediaries.

Base case (k = -1, no intermediaries allowed):

$$dp[-1][i][j] = \begin{cases} 0 & \text{if } i = j \ w(i,j) & \text{if edge } (i,j) \text{ exists} \ \infty & \text{otherwise} \end{cases}$$

Recurrence (considering vertex k as a potential intermediary):

$$dp[k][i][j] = \min(dp[k-1][i][j], \quad dp[k-1][i][k] + dp[k-1][k][j])$$

The intuition: for each pair (i, j), you face a binary choice about vertex k:

• Don’t use k: the shortest path stays dp[k-1][i][j].
• Use k: the path goes i → … → k → … → j, with cost dp[k-1][i][k] + dp[k-1][k][j].

Take the minimum of these two options. After considering all V vertices as potential intermediaries (k = 0 to V-1), dp[V-1][i][j] holds the true shortest path from i to j with no restrictions.

This is the core of Floyd-Warshall: systematically expand the set of allowed intermediate vertices, one at a time, and keep the best path found.

Space Optimization

The 3D table dp[k][i][j] uses O(V³) space, but layer k depends only on layer k-1. You can flatten this to a 2D array by updating dist[i][j] in-place:

$$dist[i][j] = \min(dist[i][j], \quad dist[i][k] + dist[k][j])$$

Why does in-place updating work? When processing intermediate vertex k, dist[i][k] and dist[k][j] are values from the “current” table. But dist[i][k] represents the shortest path from i to k using intermediaries {0, …, k}. Since k going to k doesn’t benefit from using k as an intermediary (the path from k to k via k is still 0 or the same cycle), dist[i][k] at step k equals dp[k-1][i][k]. The same reasoning applies to dist[k][j]. The in-place update is safe.

The Algorithm

void floydWarshall(int[][] dist, int V) {
    // dist[i][j] is initialized to:
    //   0 if i == j
    //   weight(i,j) if edge exists
    //   Integer.MAX_VALUE / 2 if no edge (use half to prevent overflow)

    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] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

That’s the entire algorithm. Three loops, one comparison, one update. The elegance is striking — no auxiliary data structures, no complex logic. The k loop iterates over potential intermediaries, and the i-j loops check every pair.

Initialization

int[][] initDistanceMatrix(int V, int[][] edges) {
    int INF = Integer.MAX_VALUE / 2;  // Prevent overflow during addition
    int[][] dist = new int[V][V];

    for (int[] row : dist) Arrays.fill(row, INF);
    for (int i = 0; i < V; i++) dist[i][i] = 0;

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        dist[u][v] = w;
        // For undirected: dist[v][u] = w;
    }
    return dist;
}

Use Integer.MAX_VALUE / 2 instead of Integer.MAX_VALUE to prevent integer overflow when computing dist[i][k] + dist[k][j]. This is a common bug in interview implementations.

Why the Loop Order Matters

k must be the outermost loop. This is the single most important implementation detail.

The recurrence dp[k][i][j] depends on dp[k-1][...]. If you put i or j as the outer loop by mistake, you compute paths using intermediary sets that haven’t been fully built yet. The algorithm produces incorrect results.

Think of it this way: you must fully consider “paths using vertices {0, …, k-1}” before asking “does adding vertex k improve anything?” Putting k outermost ensures this dependency is respected.

Common interview mistake: writing the loops as for i, for j, for k. This computes something, but not shortest paths. Always sanity-check: k is the outermost loop.

Path Reconstruction

The distance matrix tells you the cost of shortest paths but not the paths themselves. To reconstruct actual paths, maintain a next matrix:

int[][] next;

void floydWarshallWithPath(int[][] dist, int V) {
    next = new int[V][V];

    // Initialize: next[i][j] = j if edge (i,j) exists, -1 otherwise
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (i != j && dist[i][j] < Integer.MAX_VALUE / 2) {
                next[i][j] = j;
            } else {
                next[i][j] = -1;
            }
        }
    }

    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] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];  // Path from i to j goes through k
                }
            }
        }
    }
}

List<Integer> reconstructPath(int from, int to) {
    if (next[from][to] == -1) return List.of();  // No path

    List<Integer> path = new ArrayList<>();
    path.add(from);

    int current = from;
    while (current != to) {
        current = next[current][to];
        path.add(current);
    }
    return path;
}

next[i][j] stores the first vertex after i on the shortest path from i to j. To reconstruct the full path, follow the chain: i → next[i][j] → next[next[i][j]][j] → … → j. Each step advances one vertex closer to the destination.

Negative Cycle Detection

A negative cycle is a cycle whose total weight is negative. Traversing it repeatedly decreases the path cost without bound — shortest paths become undefined.

Floyd-Warshall detects negative cycles with a single check after the algorithm completes:

boolean hasNegativeCycle(int[][] dist, int V) {
    for (int i = 0; i < V; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

If dist[i][i] < 0 for any vertex i, it means the shortest “path” from i back to i has negative cost — a negative cycle exists through vertex i.

To find all vertices affected by negative cycles (whose shortest path distances are meaningless):

void markAffectedVertices(int[][] dist, int V) {
    int NEG_INF = Integer.MIN_VALUE / 2;

    for (int k = 0; k < V; k++) {
        if (dist[k][k] < 0) {
            // Vertex k is on a negative cycle
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // If i can reach k and k can reach j, dist[i][j] = -∞
                    if (dist[i][k] < Integer.MAX_VALUE / 2
                        && dist[k][j] < Integer.MAX_VALUE / 2) {
                        dist[i][j] = NEG_INF;
                    }
                }
            }
        }
    }
}

Any pair (i, j) where the path can detour through a negative cycle has an effectively infinite negative distance. This matters in problems like currency arbitrage detection — a negative cycle in a log-weight exchange rate graph represents a sequence of trades that yields guaranteed profit.

Complexity

Metric	Value
Time	O(V³) — three nested loops, each iterating V times
Space	O(V²) — the distance matrix
Path reconstruction	O(V²) additional space for the next matrix

The O(V³) time is independent of the number of edges E. Floyd-Warshall processes every potential intermediary for every pair, regardless of graph density. This makes it ideal for dense graphs where E ≈ V² and less competitive for sparse graphs.

Floyd-Warshall vs Alternatives

When do you use Floyd-Warshall versus running Dijkstra or Bellman-Ford from every vertex?

Approach	Time	Handles Negative Edges	Best For
Floyd-Warshall	O(V³)	Yes	Dense graphs, small V, negative edges
Dijkstra × V	O(V(V+E) log V)	No	Sparse graphs, no negative edges
Bellman-Ford × V	O(V²E)	Yes	Sparse graphs, negative edges
Johnson’s	O(V(V+E) log V)	Yes	Sparse graphs, negative edges

Floyd-Warshall wins when:

• The graph is dense (E ≈ V²), making Dijkstra × V also O(V³ log V) — worse.
• Negative edge weights are present but no negative cycles.
• V is small (≤ 400-500). The O(V³) loop is fast with small constants.
• Implementation simplicity matters. Three nested loops beats setting up V Dijkstra runs.

Dijkstra × V wins when:

• The graph is sparse (E << V²). For sparse graphs, O(V(V+E) log V) ≈ O(V² log V), far better than O(V³).
• All edge weights are non-negative.

Johnson’s Algorithm is the sophisticated choice for sparse graphs with negative edges. It reweights edges using a single Bellman-Ford pass to eliminate negative weights, then runs Dijkstra from every vertex. Time: O(V(V+E) log V). In interviews, knowing Johnson’s exists and when to use it is sufficient — implementing it from memory is rarely expected.

Transitive Closure

A related problem: determine whether vertex i can reach vertex j for all pairs (i, j). This is the transitive closure of the graph.

Floyd-Warshall adapts to this by replacing arithmetic with boolean logic:

void transitiveClosure(boolean[][] reach, int V) {
    // Initialize: reach[i][j] = true if edge (i,j) exists or i == j

    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }
}

Replace min with ||, and + with &&. The recurrence becomes: “can i reach j directly or through k?” After processing all intermediaries, reach[i][j] tells you whether any path from i to j exists.

This is useful for:

• Checking if a directed graph is strongly connected (every pair is mutually reachable).
• Answering reachability queries in O(1) after O(V³) preprocessing.
• Dependency resolution — “does changing module A affect module B?”

Applications

Network Routing

Interior gateway protocols like OSPF compute routing tables that require shortest paths between all routers. Floyd-Warshall suits small-to-medium networks where the router count V is manageable.

Currency Arbitrage

Model currencies as vertices and exchange rates as edges. The weight of edge (A, B) is -log(rate(A → B)). A negative cycle in this graph means multiplying exchange rates along the cycle yields > 1 — a guaranteed profit opportunity.

USD → EUR → GBP → USD

If rate(USD→EUR) × rate(EUR→GBP) × rate(GBP→USD) > 1.0
then -log(r1) - log(r2) - log(r3) < 0 → negative cycle detected

Floyd-Warshall with negative cycle detection directly identifies these arbitrage opportunities.

Shortest Paths in Game Worlds

For small game maps (V < 500), precompute all-pairs shortest paths during level loading. Runtime pathfinding queries then take O(path length) using the next matrix — ideal for real-time games where latency matters.

Complete Implementation

Here’s a production-ready Floyd-Warshall with all features:

record FloydWarshallResult(int[][] dist, int[][] next, boolean hasNegativeCycle) {}

FloydWarshallResult floydWarshall(int V, int[][] edges) {
    int INF = Integer.MAX_VALUE / 2;

    // Initialize distance and next matrices
    int[][] dist = new int[V][V];
    int[][] next = new int[V][V];

    for (int i = 0; i < V; i++) {
        Arrays.fill(dist[i], INF);
        Arrays.fill(next[i], -1);
        dist[i][i] = 0;
    }

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        dist[u][v] = w;
        next[u][v] = v;
    }

    // Floyd-Warshall core
    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] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }

    // Check for negative cycles
    boolean negativeCycle = false;
    for (int i = 0; i < V; i++) {
        if (dist[i][i] < 0) {
            negativeCycle = true;
            break;
        }
    }

    return new FloydWarshallResult(dist, next, negativeCycle);
}

The record-based return type bundles everything the caller needs: distances, path reconstruction data, and negative cycle status. Clean, readable, and interview-ready.

Interviewer Tips

“Explain Floyd-Warshall in one sentence.” Floyd-Warshall computes shortest paths between all vertex pairs using dynamic programming, systematically considering each vertex as a potential intermediary.

“Why is k the outer loop?” The DP recurrence builds on the subproblem “shortest path using intermediaries {0, …, k-1}.” Vertex k must be fully processed before moving to k+1. Putting k inside breaks this dependency chain.

“When would you use Floyd-Warshall over running Dijkstra V times?” Three situations: when the graph has negative edge weights (Dijkstra can’t handle those), when the graph is dense (Floyd-Warshall’s O(V³) beats Dijkstra’s O(V³ log V)), or when implementation simplicity matters (three nested loops vs. managing V priority queues).

“How do you detect negative cycles?” After running Floyd-Warshall, check every diagonal entry dist[i][i]. If any is negative, vertex i lies on a negative cycle. The shortest “path” from i to i has negative cost, meaning you can loop around and reduce cost indefinitely.

“Can Floyd-Warshall handle undirected graphs?” Yes. Model each undirected edge (u, v, w) as two directed edges: (u, v, w) and (v, u, w). The algorithm works on directed graphs, and an undirected graph is a special case with symmetric edges. Watch out for negative-weight undirected edges — they always create a negative cycle (traverse the edge back and forth).