Floyd-Warshall algorithm explained: how it works, code and complexity

What problem Floyd-Warshall solves

Sometimes you need the distance between all pairs of places, not just from one start: a table of travel times between all cities, the latency between every pair of servers, or the full reachability of a dependency graph. Floyd-Warshall solves this all-pairs shortest path problem with a very short dynamic programming algorithm.

It was published by Robert Floyd in 1962 ("Algorithm 97: Shortest path"), building on Stephen Warshall's 1962 algorithm for transitive closure.

The idea in plain words

Number the nodes 0 to V − 1. After processing node k, dist[i][j] is the shortest path from i to j that uses only nodes 0 to k as intermediate stops. Allowing one more intermediate node k gives two options: the old best path that avoids k, or a path i → k → j made of two best paths that already only use nodes before k.

1. Fill the matrix: 0 on the diagonal, the edge weight where an edge exists, infinity elsewhere.
2. For k = 0 to V − 1, for every pair (i, j): if dist[i][k] + dist[k][j] < dist[i][j], update it.
3. After the last k, the matrix holds all shortest distances. A negative value on the diagonal means a negative cycle.

The order of the loops is essential: k must be the outer loop.

Worked example, step by step

Directed graph with 4 nodes and edges 0→1 (3), 0→3 (7), 1→0 (8), 1→2 (2), 2→0 (5), 2→3 (1), 3→0 (2). Start matrix (row = from, column = to):

1. k = 0: paths may pass through node 0. 1→3 becomes 8 + 7 = 15, 2→1 becomes 5 + 3 = 8 and 3→1 becomes 2 + 3 = 5.
2. k = 1: through node 1. 0→2 becomes 3 + 2 = 5 and 3→2 becomes 5 + 2 = 7.
3. k = 2: through node 2. 0→3 improves from 7 to 5 + 1 = 6, 1→3 from 15 to 2 + 1 = 3, and 1→0 from 8 to 2 + 5 = 7.
4. k = 3: through node 3. 1→0 improves from 7 to 3 + 2 = 5, 2→0 from 5 to 1 + 2 = 3, and 2→1 from 8 to 1 + 5 = 6.

Final matrix rows: 0 → [0, 3, 5, 6], 1 → [5, 0, 2, 3], 2 → [3, 6, 0, 1], 3 → [2, 5, 7, 0].

Python implementation

INF = float("inf")
def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            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]
    return dist, nxt
edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2),
         (2, 0, 5), (2, 3, 1), (3, 0, 2)]
dist, nxt = floyd_warshall(4, edges)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

The nxt matrix stores the first step on the best path from i to j, which is enough to rebuild any path:

def path(nxt, i, j):
    if nxt[i][j] is None:
        return []                         # no path
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route
print(path(nxt, 1, 0))  # [1, 2, 3, 0]

If you have many nodes and want speed in Python, the same triple loop can be written with NumPy as one vectorized update per k: d = np.minimum(d, d[:, k, None] + d[None, k, :]).

Time and space complexity

For sparse graphs with non-negative weights, running Dijkstra from every node costs O(V × (V + E) log V), which is faster than O(V³) when E is much smaller than V².

Variants and common mistakes

• Negative cycles: after the loops, if dist[i][i] < 0 for some i, node i lies on a negative cycle and shortest paths through it are undefined.
• Transitive closure (Warshall): use booleans and replace min/plus with or/and: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]).
• Minimax and maximin paths: replace + with max (or min) to find, for example, the path whose largest edge is as small as possible.
• Use a large finite number instead of infinity only if you are sure that the sum of two of them cannot overflow; in Python, float("inf") is the safe choice.
• Initialize the diagonal to 0, and when there are parallel edges keep the smallest weight.

When to use it and real-world uses

• Precomputing a distance table between all stations, warehouses or cities for later lookups.
• Graph analytics such as closeness centrality or the diameter of a small network.
• Interview problems: find the city with the smallest number of neighbors within a distance threshold, evaluate division (ratios as path products), course prerequisites as transitive closure.