Dijkstra and Bellman-Ford answer the question «how far is every vertex from this source?». Sometimes, though, you need the full table: the distance between every pair of vertices. This is the case of the classic mileage table printed on old road maps, of a matrix of travel times between the warehouses of a logistics company, or of the analysis of a corporate network where you want to know how many hops separate every pair of machines.
The Floyd-Warshall algorithm solves this problem with a few lines of code that can be written from memory and rarely contain bugs.
The idea: allowing intermediate vertices one at a time
Number the vertices from 0 to n − 1. Let D_k(i, j) be the length of the shortest path from i to j that uses as intermediate vertices only those with index less than k.
- With k = 0 no intermediates are allowed: D_0(i, j) is the weight of the direct edge, or infinity if there is none.
- Going from k to k + 1, vertex k is allowed as well. The best path either does not use it (and stays D_k(i, j)), or passes through it exactly once: from i to k and then from k to j.
Therefore:
D_{k+1}(i, j) = min( D_k(i, j), D_k(i, k) + D_k(k, j) )
Once all vertices have been allowed, you have the true shortest distances. It is a clear example of dynamic programming: a large problem solved by combining smaller subproblems, in an order that guarantees what is needed has already been computed.
The code
A single matrix is enough, updated in place:
def floyd_warshall(D):
n = len(D)
for k in range(n):
for i in range(n):
dik = D[i][k]
if dik == float("inf"):
continue
for j in range(n):
if dik + D[k][j] < D[i][j]:
D[i][j] = dik + D[k][j]
return D
The order of the loops is crucial: k must be the outermost loop. Swapping it with i or j is a classic mistake that produces wrong results without any error message.
The initial matrix has 0 on the diagonal, the edge weight where an edge exists and infinity elsewhere. If there are several edges between two vertices, keep the lightest.
Rebuilding the paths
Distances alone are often not enough: you also want to know which way to go. Keep a second matrix succ, where succ[i][j] is the first vertex to visit after i on the way to j. Initially succ[i][j] = j for every existing edge; whenever going through k improves the pair (i, j), set succ[i][j] = succ[i][k]. To rebuild the path, start from i and follow succ until you reach j.
Negative weights and negative cycles
Floyd-Warshall accepts edges with negative weight. If there is a negative cycle, at the end at least one element of the diagonal is less than zero: a vertex is «less than zero away from itself». Checking the diagonal is therefore enough to know whether the results can be trusted.
Cost and limits
Three nested loops over n vertices: time is proportional to n³ and memory to n². Some orders of magnitude:
| Vertices | Matrix cells | Inner-loop iterations |
|---|---|---|
| 100 | 10 thousand | 1 million |
| 1,000 | 1 million | 1 billion |
| 10,000 | 100 million | 1,000 billion |
Up to a few hundred vertices it is instantaneous even in Python; at a few thousand it becomes heavy without numerical libraries; beyond that, change approach. For large sparse graphs it is much better to run Dijkstra from every vertex, at a total cost of roughly n · (n + m) log n, or Johnson's algorithm if there are negative weights.
A useful variant: transitive closure
By replacing the sum with logical «and» and the minimum with logical «or», the same scheme answers the question «can j be reached from i?». You get the transitive closure of the graph, also known as Warshall's algorithm.
Practical examples:
- in a permission system where roles inherit from other roles, the closure tells you which permissions each role actually has;
- in a network with firewall rules, it tells you which segments can communicate, including through other segments;
- in an organisation chart, it tells you who is above whom, at any level.
In short
- Floyd-Warshall computes the shortest distances between all pairs of vertices.
- It allows intermediate vertices one at a time: it is dynamic programming.
- The loop over k must be the outermost; the cost is n³ in time and n² in memory.
- It accepts negative weights; a negative value on the diagonal signals a negative cycle.
- With logical operations instead of sum and minimum it computes the transitive closure.
