Floyd-WarshallAll-pairs shortest paths

01Why it exists

Reach for it when you see:Shortest distances between all pairs, a few hundred nodes at most, a dense graph, negative edges but no negative cycle, reachability or transitive closure, bottleneck paths, a lot of point-to-point queries.

02The core idea

All-pairs shortest paths means computing the shortest distance for every pair (i, j). You could run Dijkstra once from each node, but that breaks down on negative edges; running Bellman-Ford from each node instead costs O(V²E). Floyd-Warshall solves the whole thing with dynamic programming, and the code is nothing but three nested loops. Define the state as: d_k[i][j] is the shortest distance from i to j using only the first k nodes as intermediates. At k = 0 no intermediate is allowed, so it is just the original edges; once all V nodes are allowed, it is the real answer.

Going from d_(k−1) to d_k only requires thinking about the newly admitted node k. Either the shortest path does not pass through k, and the distance is still d_(k−1)[i][j]; or it does, and since a shortest path never revisits a node when there is no negative cycle, it passes through k exactly once. That splits it into i to k and k to j, each using only the first k − 1 nodes as intermediates: d_k[i][j] = min(d_(k−1)[i][j], d_(k−1)[i][k] + d_(k−1)[k][j]). k has to be the outermost loop. The three-dimensional table collapses into a single two-dimensional matrix updated in place, because during round k neither row k nor column k changes: in d[i][k] + d[k][k], d[k][k] = 0.

Time is O(V³) and space is O(V²). V = 500 is about 125 million simple operations, under a second in C++; a few thousand nodes is already too slow, and for a sparse graph with no negative weights you would run Dijkstra from each node instead, at O(V·E log V). When it finishes, any d[i][i] < 0 means i can walk back to itself for a negative total — a negative cycle. To recover paths, keep a second table next[i][j] holding the first step from i towards j, and set next[i][j] = next[i][k] whenever you update. Swap addition and minimum for other operations and the same skeleton computes transitive closure (AND, OR) and widest bottleneck paths (min, max).

The usual traps: putting k in an inner loop, which does not give shortest distances at all; using INT_MAX as infinity, so that two of them overflow when added, or ∞ plus a negative weight ends up looking smaller than ∞ and invents a path that does not exist — which is why both halves must be checked against ∞ first; forgetting to set d[i][i] to 0; not taking the minimum when a pair of nodes has several edges; and filling in only one direction for an undirected graph. With a negative cycle present the matrix values are meaningless, and they keep shrinking, badly enough to overflow. How it relates to its neighbours: Dijkstra and Bellman-Ford are single-source while Floyd-Warshall is all-pairs; it works on the adjacency matrix representation; and a state of "only the first k nodes may be intermediates" is a very typical piece of DP design.

03The algorithm

1. 1Build the V × V matrix dist: dist[i][i] = 0, each edge u → v set to min(current value, w), everything else ∞. If you want to recover paths, also set next[u][v] = v.
2. 2The outermost loop runs k from 0 to V − 1, meaning "k is now allowed as an intermediate node".
3. 3The two inner loops enumerate i and j: if neither dist[i][k] nor dist[k][j] is ∞ and their sum is smaller than dist[i][j], update dist[i][j] and set next[i][j] = next[i][k].
4. 4Once the triple loop finishes, check the diagonal: any dist[i][i] < 0 means the graph contains a negative cycle.
5. 5To query a distance, read dist[i][j]; to get the path, start at i and repeatedly move to next[current][j] until you arrive at j.

04Interactive demo

Four nodes and eight directed edges, where B → C has weight −2. The distance matrix on the right starts out holding only the direct edges. Each round first fixes the intermediate node k (the yellow node, with row k and column k of the matrix outlined in yellow), then steps through the cells this round shrinks: blue is the dist[i][j] being updated, solid yellow are the dist[i][k] and dist[k][j] it reads, and green marks the cells already updated this round. k = A lets C and D reach B through A; k = B puts the negative edge to work, taking A → C from ∞ to 2 and D → C from 8 to 3; k = C and k = D change three cells each, with B → A and C → B both updated twice. Finally the diagonal is checked for negatives, and the next table reconstructs the shortest path from D to C: D → A → B → C, total length 3.

05Code

Python has the full version: handling duplicate edges, recording next to recover paths, and checking for negative cycles, plus a Warshall transitive closure over bitsets using role inheritance as the example. C++ has the shortest-distance version updating in place, with INF set to a quarter of the maximum so sums cannot overflow, and a widest-path variant that swaps the operations for min and max.

INF = float("inf")


def floyd_warshall(n, edges):
    """Returns (dist, nxt): dist[i][j] is the shortest distance from i to j, nxt[i][j] the next node after i on that path. O(V³)"""
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[i if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        if w < dist[u][v]:                      # keep the smallest when a pair has several edges
            dist[u][v] = w
            nxt[u][v] = v
    for k in range(n):                          # k must be the outermost loop
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]       # head towards k first
    return dist, nxt


def has_negative_cycle(dist):
    return any(dist[i][i] < 0 for i in range(len(dist)))


def get_path(nxt, u, v):
    if nxt[u][v] is None:                       # unreachable
        return []
    path = [u]
    while u != v:
        u = nxt[u][v]
        path.append(u)
    return path


def transitive_closure(n, edges):
    """Warshall: bit j of reach[i] says whether i can reach j. Integers act as bitsets, so one OR handles a whole row"""
    reach = [1 << i for i in range(n)]
    for u, v in edges:
        reach[u] |= 1 << v
    for k in range(n):
        for i in range(n):
            if reach[i] >> k & 1:               # i reaches k, so i reaches everything k reaches
                reach[i] |= reach[k]
    return reach


if __name__ == "__main__":
    A, B, C, D = range(4)
    edges = [(A, B, 4), (A, D, 9), (D, A, 1), (B, C, -2), (B, D, 5), (C, D, 3), (D, C, 8), (C, A, 6)]
    dist, nxt = floyd_warshall(4, edges)
    for row in dist:
        print(row)                              # [0, 4, 2, 5] / [2, 0, -2, 1] / [4, 8, 0, 3] / [1, 5, 3, 0]
    print("".join("ABCD"[x] for x in get_path(nxt, D, C)))   # DABC
    bad = [(u, v, -9 if (u, v) == (B, C) else w) for u, v, w in edges]
    print(has_negative_cycle(floyd_warshall(4, bad)[0]))      # True: B → C → D → A → B sums to -1

    roles = ["admin", "editor", "viewer", "auditor"]
    reach = transitive_closure(4, [(0, 1), (1, 2), (3, 2)])  # admin inherits editor, editor inherits viewer
    print([roles[j] for j in range(4) if reach[0] >> j & 1])  # ['admin', 'editor', 'viewer']

06Practice

• LeetCode 1334Find the City With the Smallest Number of Neighbors at a Threshold DistanceMedium
• LeetCode 1462Course Schedule IV (transitive closure)Medium
• LeetCode 399Evaluate Division (Floyd-Warshall with addition swapped for multiplication)Medium
• LeetCode 2976Minimum Cost to Convert String I (cheapest conversions between 26 letters)Medium
• LeetCode 2959Number of Possible Sets of Closing Branches (enumerate subsets, running Floyd-Warshall on each)Hard
• LeetCode 2977Minimum Cost to Convert String IIHard