Graph AlgosAlgorithmaka all-pairs shortest paths, APSP, Roy-Floyd

Floyd-Warshall

All-pairs shortest paths by dynamic programming over the set of allowed intermediate nodes: three nested loops, O(V³), handles negative edges.

▶ VisualizePattern: Dynamic ProgrammingPractice (1)
Progress

Overview

Floyd-Warshall computes the shortest distance between every pair of nodes using an Adjacency Matrix and a single idea: d[i][j] after considering intermediate nodes {0..k} equals min(d[i][j], d[i][k] + d[k][j]) computed with intermediates {0..k-1}. Three nested loops, k outermost, and the matrix updates in place.

Preconditions and complexity: any weights including negative (no negative cycles for meaningful distances, but they are detectable via d[i][i] < 0), directed or undirected. Time O(V³), space O(V²). It is the right choice for dense graphs or when V ≤ ~400–500 and you need all pairs; on sparse graphs, running Dijkstra's Algorithm from every node costs O(V (V + E) log V), which is far less when E ≪ V².

all pairsshortest pathdynamic programmingdensenegative edgesO(V³)

Intuition

A mental model before the formal terms.

You have a table of direct flight prices between every pair of cities. Now open hub 0: for every pair, ask "is going via hub 0 cheaper than what I have?" and update the table. Then open hub 1, then hub 2, … After the last hub is opened, every entry is the cheapest itinerary using any combination of hubs. The order in which you open hubs is exactly the outer k loop, and it must be outermost — you must finish considering one hub for all pairs before opening the next.

How it works

  1. Initialise d[i][i] = 0, d[i][j] = w(i, j) for edges (keep the minimum for parallel edges), ∞ otherwise. Set next[i][j] = j for edges to support path reconstruction.
  2. For k in 0..V-1 (outermost): for every i, for every j: if d[i][k] + d[k][j] < d[i][j], set d[i][j] to that sum and next[i][j] = next[i][k].
  3. After the loops, d[i][j] is the shortest distance. If any d[i][i] < 0, a negative cycle passes through i; every pair that can reach and leave such a node has distance -∞.
  4. Path from i to j: start at i, repeatedly move to next[cur][j] until cur == j.
  5. Loop order matters: with k inside, the update d[i][j] via k would use a d[i][k] that has not yet been allowed to use intermediates < k for all rows, breaking the DP. i and j are interchangeable; only k must be outermost.

Why it works

Define D_k[i][j] = shortest path from i to j whose intermediate nodes all lie in {0, …, k-1}. Either the optimal such path avoids node k-1 (D_{k-1}[i][j]) or it passes through it exactly once (D_{k-1}[i][k-1] + D_{k-1}[k-1][j]). That is the recurrence; D_0 is the edge matrix and D_V is the answer.

In-place update is safe because in round k, d[i][k] and d[k][j] do not change: d[i][k] = min(d[i][k], d[i][k] + d[k][k]) and d[k][k] = 0 (absent negative cycles), so row k and column k are fixed points during round k.

Negative cycle detection: a cycle through i of negative total weight makes d[i][i] negative once every node on the cycle has been used as k.

Recognition

How to tell a problem wants this.

  • "Distance between every pair", "for each query (u, v)", many queries on a small graph.
  • V ≤ 500 in the constraints — a strong hint that O(V³) is intended.
  • Transitive closure (reachability for all pairs) — same loops with boolean OR/AND.
  • Minimax/maximin path between all pairs (replace + with max and min with min/max).
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

ABCDE
A03∞∞8
B∞017∞
C2∞01∞
D∞∞∞02
E4∞∞∞0
1/39Initialize the 5×5 matrix from the edge weights: 0 on the diagonal, ∞ where no edge exists. dist[i][j] means "best path from i to j using no intermediate nodes yet".
Row k / column k (paths through k)Cell being updatedImproved in this k-phaseDiagonal (always 0)
PseudocodeLearn Floyd-Warshall →
1dist[i][j] = w(i,j) if edge, 0 if i == j, else ∞
2for k in nodes:          # allowed intermediate
3  for i in nodes:
4    for j in nodes:
5      if dist[i][k] + dist[k][j] < dist[i][j]:
6        dist[i][j] = dist[i][k] + dist[k][j]
7return dist
Complexity
best O(V³)
avg O(V³)
worst O(V³)
space O(V²)
Speed

Pseudocode

1d = adjacency matrix with INF for missing edges, d[i][i] = 0
2for k in 0..n-1:
3  for i in 0..n-1:
4    for j in 0..n-1:
5      if d[i][k] + d[k][j] < d[i][j]:
6        d[i][j] = d[i][k] + d[k][j]; next[i][j] = next[i][k]
7negative cycle iff any d[i][i] < 0

Implementations

1from math import inf
2 
3 
4def floyd_warshall(
5    n: int, edges: list[tuple[int, int, int]]
6) -> tuple[list[list[float]], list[list[int]]]:
7    """edges = directed (u, v, w) triples; nodes 0..n-1.
8    Returns (dist, nxt): all-pairs distances (inf = unreachable) and
9    nxt[i][j] = first hop on the shortest i -> j path (-1 = unreachable)."""
101 · Initialize distance and next-hop matrices
11    dist: list[list[float]] = [[inf] * n for _ in range(n)]
12    nxt = [[-1] * n for _ in range(n)]
13    for i in range(n):
14        dist[i][i] = 0
15        nxt[i][i] = i
162 · Seed direct edges (keep the minimum over parallel edges)
17    for u, v, w in edges:
18        if w < dist[u][v]:
19            dist[u][v] = w
20            nxt[u][v] = v
213 · Allow each node k as an intermediate (k must be the outer loop)
22    for k in range(n):
23        row_k = dist[k]                    # hoist row lookups out of the inner loop
24        for i in range(n):
25            d_ik = dist[i][k]
26            if d_ik == inf:                # row skip: nothing goes through k from i
27                continue
28            row_i = dist[i]
29            for j in range(n):
30                cand = d_ik + row_k[j]
31                if cand < row_i[j]:
32                    row_i[j] = cand
33                    nxt[i][j] = nxt[i][k]
34    return dist, nxt
35 
36 
374 · Reconstruct a path by following next hops
38def fw_path(nxt: list[list[int]], u: int, v: int) -> list[int]:
39    if nxt[u][v] == -1:
40        return []
41    path = [u]
42    while u != v:
43        u = nxt[u][v]
44        path.append(u)
45    return path
46 
47 
485 · Negative cycle iff some diagonal entry went negative
49def has_negative_cycle(dist: list[list[float]]) -> bool:
50    return any(dist[i][i] < 0 for i in range(len(dist)))
Walkthrough
  1. Matrices are built with list comprehensions — [[inf] * n for _ in range(n)] creates n independent rows.
  2. Hoisting row_k = dist[k] and row_i = dist[i] out of the inner loop avoids repeated list indexing, roughly halving the runtime in CPython.
  3. The d_ik == inf skip removes entire inner loops for unreachable (i, k) pairs.
  4. fw_path walks the nxt matrix; has_negative_cycle scans the diagonal with a generator expression.
Complexity (this implementation)
time O(V³) · space O(V²)

Pure-Python triple loops manage ~10⁷ iterations per second: V = 200 is fine, V = 500 (1.25·10⁸) takes tens of seconds — reach for numpy (repeated np.minimum over broadcasts) beyond that.

Language notes
  • [[inf] * n] * n would alias one row n times — the comprehension is mandatory.
  • A numpy formulation does round k as d = np.minimum(d, d[:, k:k+1] + d[k]), vectorising the two inner loops.
  • inf is a float; if exact integer distances matter downstream, replace reachable entries with int(...) at the end.
Common mistakes in this language
  • Row aliasing via * n on a list of lists.
  • Not hoisting row references and wondering why Python is 3x slower than expected.
  • Using a huge int like 10**18 as INF and forgetting it silently participates in comparisons as a real value after one bad addition.
Language differences that matter here
  • Infinity: JS/TS Infinity and Python math.inf absorb addition, so INF + INF is harmless; C++ must shrink its integer sentinel (MAX/4) or guard every addition — long long overflow is undefined behaviour.
  • 2D-array construction pitfalls differ: Python [[inf] * n] * n and JS Array(n).fill(row) both alias a single row object; C++ vector construction copies properly by design.
  • Inner-loop speed: C++ runs V=500 in well under a second; JS/TS manage it in hundreds of ms; CPython needs row-hoisting and still struggles past V≈300 — numpy vectorisation is the practical fix.
  • The k-outermost loop order is an algorithmic invariant in all four languages — no compiler or type system can catch it if you get it wrong.

Complexity

Best
O(V³)
Average
O(V³)
Worst
O(V³)
Space
O(V²)

No early exit. V = 500 → 1.25·10^8 inner iterations, fine; V = 5000 → 1.25·10^11, infeasible. Constant factor is tiny (no heap, cache-friendly row access).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • All-pairs distances on a small (V ≤ ~500) or dense graph.
  • Negative edges are present and you need all pairs (Dijkstra-from-every-node is invalid).
  • Many distance queries after a one-time precomputation.
  • Transitive closure, minimax paths, or any semiring variant — same triple loop with different operators.
Avoid it when

Alternatives

Dijkstra's AlgorithmBellman-FordBFS Shortest Path (Unweighted)

Common mistakes

  • Putting k in the inner loop — produces wrong (too large) distances on many graphs.
  • Adding INF + INF in fixed-width integers → overflow into negative "improvements". Guard d[i][k] != INF and use INF = MAX/4, or use floating Infinity.
  • Not taking the minimum over parallel edges during initialisation.
  • Reconstructing the path with a prev matrix but updating it as if it were next (or vice versa) — next[i][j] = next[i][k] versus prev[i][j] = prev[k][j].
  • Reporting finite distances for pairs affected by a negative cycle; check d[i][i] < 0 and propagate -∞ if the task requires it.

Interview patterns

  • "Find the city with the smallest number of neighbours within distance threshold" — Floyd-Warshall then count per row.
  • Transitive closure: reach[i][j] |= reach[i][k] && reach[k][j] (course prerequisites queries).
  • Widest/bottleneck path for all pairs: d[i][j] = max(d[i][j], min(d[i][k], d[k][j])).
  • Shortest cycle (girth) in a weighted digraph: minimum d[i][i] after the loops when self-distances are initialised to ∞.
Interview questions on this
Mock interviews

Example problems

Network Delay Timemedium