Floyd-Warshall — All-Pairs Shortest Path in O(V^3) [LC 1334, Google, Amazon]

Problem Statement#

Given a weighted directed graph with n vertices, compute the shortest distance between every pair of vertices. Edge weights may be negative; if a negative cycle is reachable, report that no shortest distances exist for paths involving that cycle. Use the Floyd-Warshall algorithm — a triple-nested dynamic programming routine running in O(V^3).

Constraints:

• 1 <= n <= 400 (Floyd-Warshall is impractical beyond a few hundred vertices)
• Edge weights in range [-10^4, 10^4]
• The graph may have negative edges but a problem-specific assumption may forbid negative cycles.

Example:

Input:  n = 4, edges = [[0,1,3],[0,3,7],[1,0,8],[1,2,2],[2,0,5],[2,3,1],[3,0,2]]
Output: dist matrix:
        [[0, 3, 5, 6],
         [5, 0, 2, 3],
         [3, 6, 0, 1],
         [2, 5, 7, 0]]
Explanation: dist[1][3] = 1 -> 2 -> 3 = 2 + 1 = 3.

Why This Problem Matters#

Floyd-Warshall is the canonical answer when an interviewer says "compute shortest paths between every pair of vertices." Although Dijkstra-from-every-source can match its asymptotic complexity for sparse graphs (O(V * (E + V) log V)), Floyd-Warshall wins on simplicity, on dense graphs, and on graphs with negative edges where Dijkstra cannot run.

LeetCode 1334 (Find the City With the Smallest Number of Neighbors at a Threshold Distance) is the textbook FAANG interview rendering. LeetCode 399 (Evaluate Division), LeetCode 743 (Network Delay Time), and LeetCode 787 (Cheapest Flights Within K Stops) all admit Floyd-Warshall solutions when V is small. Game development uses it for precomputed routing on map graphs; database query optimizers use it on join graphs.

The algorithm is also a clean illustration of dynamic programming on graphs. Each iteration extends the set of allowed intermediate vertices, and the recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) is one of the cleanest DP transitions in all of algorithms.

The Core Insight#

Floyd-Warshall fills a dist[i][j] matrix where dist[i][j] will eventually hold the shortest distance from i to j. Initially, dist[i][j] is the direct edge weight, 0 on the diagonal, and infinity elsewhere.

The key idea: define dist_k[i][j] as the shortest path from i to j using only vertices {0, 1, ..., k} as intermediate stops. Then:

dist_k[i][j] = min(dist_{k-1}[i][j],
                   dist_{k-1}[i][k] + dist_{k-1}[k][j])

That is, either you do not use k as an intermediate (the first term) or you do (the second term, going through k as the new midpoint).

The space-saving trick: you only need a single 2D matrix because when you update entry (i, j) using row k and column k, those reference values are not modified by your update. So the in-place algorithm with the loop ordering k -> i -> j is correct.

After the loop with k ranging from 0 to n-1, dist[i][j] holds the true all-pairs shortest distance. To detect a negative cycle, check whether any dist[i][i] < 0. If so, vertex i lies on a negative cycle and shortest distances using i are undefined.

Visual Dry Run#

n = 3, edges: 0->1 (4), 0->2 (5), 1->2 (-3).

Initial dist matrix (INF means infinity):

After k = 0 (allow vertex 0 as midpoint): no improvement because no row goes through 0 as intermediate beyond direct edges.

After k = 1 (allow vertex 1 as midpoint): dist[0][2] = min(5, dist[0][1]+dist[1][2]) = min(5, 4 + (-3)) = 1.

After k = 2: no further improvement. Final answer: 0->1 = 4, 0->2 = 1, 1->2 = -3.

Solution (Optimal)#

Python#

def floyd_warshall(n, edges):
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # handle multi-edges by taking min
 
    # Triple loop: k must be the OUTERMOST loop
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue  # micro-optimisation: nothing to gain
            for j in range(n):
                if dist[k][j] == INF:
                    continue
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
 
    # Detect negative cycle: any vertex with dist[i][i] < 0
    for i in range(n):
        if dist[i][i] < 0:
            return None  # negative cycle present
    return dist

JavaScript#

function floydWarshall(n, edges) {
    const INF = Infinity;
    const dist = Array.from({ length: n }, () => new Array(n).fill(INF));
    for (let i = 0; i < n; i++) dist[i][i] = 0;
    for (const [u, v, w] of edges) {
        if (w < dist[u][v]) dist[u][v] = w;
    }
 
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            if (dist[i][k] === INF) continue;
            for (let j = 0; j < n; j++) {
                if (dist[k][j] === INF) continue;
                const through = dist[i][k] + dist[k][j];
                if (through < dist[i][j]) dist[i][j] = through;
            }
        }
    }
 
    for (let i = 0; i < n; i++) {
        if (dist[i][i] < 0) return null; // negative cycle
    }
    return dist;
}

Complexity: Time O(V^3). Space O(V^2) for the distance matrix.

Common Mistakes#

1. Wrong loop order. The outermost loop must be k. If you put i outermost, the recurrence references stale values and the answer is wrong. Memorise: "k, i, j."
2. Forgetting the diagonal. dist[i][i] = 0 for all i is part of initialization. Without it, the algorithm cannot use a vertex as a midpoint without paying a phantom cost.
3. Overflow on negative paths. If you sum dist[i][k] + dist[k][j] while one is INF, you may overflow. Guard with the INF check shown above.
4. Misreading negative cycles. Floyd-Warshall does not give meaningful distances for vertex pairs whose shortest path passes through a negative cycle. The simplest check is dist[i][i] < 0. A more thorough check sets distances to -INF along all such pairs.
5. Using on huge graphs. V = 1000 is already 10^9 ops — too slow. Beyond a few hundred vertices, prefer Johnson's algorithm or Dijkstra-from-every-vertex.
6. Multi-edges and self-loops. Take the min over all parallel edges during initialization; ignore non-negative self-loops.

Interview Tips#

• Always state the V^3 cost and check the constraints. If n is small (around 400 or less), Floyd-Warshall is the most code-efficient solution.
• Mention the negative-cycle detection as a free byproduct.
• Compare against Dijkstra-from-every-source: same asymptotic for dense graphs, but Dijkstra handles non-negative weights only.
• When the problem also asks for path reconstruction, maintain a next[i][j] matrix: when you update dist[i][j] via k, set next[i][j] = next[i][k]. Reconstruction walks the chain.
• Floyd-Warshall is also the algorithm of choice for transitive closure: replace min/+ with or/and to compute reachability.

Follow-up Questions#

1. What is Johnson's algorithm and when is it better? It runs Bellman-Ford once to reweight edges, then Dijkstra from every vertex. For sparse graphs, it is O(VE log V), beating Floyd-Warshall.
2. How to reconstruct the actual shortest path? Maintain next[i][j] during updates and walk it.
3. LeetCode 1334: Compute all-pairs shortest paths, then for each vertex count how many destinations have dist <= threshold.
4. What about the longest path? Floyd-Warshall trivially computes longest paths if there are no positive cycles, by negating weights.
5. Transitive closure: Replace min with or and + with and to determine reachability. Same O(V^3) cost.

Key Takeaways#

• Floyd-Warshall computes all-pairs shortest paths in O(V^3) time and O(V^2) space.
• The recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) with k as the outermost loop is the entire algorithm.
• Handles negative edge weights and detects negative cycles via dist[i][i] < 0.
• Best for dense graphs and small V (up to a few hundred). Beyond that, prefer Johnson's algorithm.
• Path reconstruction needs an auxiliary next[i][j] matrix updated alongside distances.
• FAANG cue: any problem with "all-pairs", "between every pair", or "any source any destination" plus tiny V calls for Floyd-Warshall.