Floyd-Warshall Algorithm

#How does it work?

Floyd-Warshall computes shortest paths between every pair of nodes, not just from one start. The result is a V × V distance matrix: dist[i][j] is the cost of the shortest path from i to j.

The idea is dynamic programming: it allows nodes as "stops in between" one at a time. After round k, the best route from i to j using only the first k nodes as stops is known; the new question is whether going via k, dist[i][k] + dist[k][j], beats the current dist[i][j].

The code is just three nested loops, and it handles negative edges too (as long as there is no negative cycle). A negative value on the diagonal means there is a negative cycle.

#Try it yourself

#Step by step

1. 01Fill the matrix with direct edge weights: 0 on the diagonal, ∞ where there is no edge.
2. 02For each node k (the outermost loop):
3. 03 for each pair i, j: if dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j].
4. 04To rebuild paths, keep a next[i][j] (first stop) table.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

INF = float("inf")

EDGES = [(1, 2, 4), (1, 3, 1), (2, 4, 5), (2, 5, 2), (3, 5, 2), (3, 6, 4), (4, 7, 3), (5, 7, 6), (6, 7, 1)]
N = 7

# dist[i][j] starts as the direct edge weight: 0 on the diagonal, INF where there is no edge.
dist = [[0 if i == j else INF for j in range(N)] for i in range(N)]
for a, b, w in EDGES:
    dist[a - 1][b - 1] = dist[b - 1][a - 1] = w  # undirected

for k in range(N):  # k must be the outermost loop
    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]

for row in dist:
    print(" ".join(map(str, row)))

#Complexity

It takes V³ steps no matter how many edges there are. It is very practical for small, dense graphs (a few hundred nodes). For large sparse graphs, running Dijkstra from every node (O(V · E log V)) is faster. The k loop must be the outermost; reordering the loops gives wrong results.

#When to use it?

Whenever distances between all pairs are needed: distance tables between cities, latency between every pair of devices in a network, the transitive closure of a graph (who can reach whom) and precomputed path tables for game maps.

#Practice

Log in to answer questions and save your progress.