Understanding the Floyd-Warshall algorithm for all-pairs distances
Shortest-path questions arise whenever a route must be chosen between several places. A delivery driver needs the quickest path to a parcel, a game maps connected rooms, and a dependency graph needs the fewest steps between components. Floyd-Warshall answers this class of question by finding the minimum total edge weight between every ordered pair of vertices. Its result is an all-pairs shortest-path distance matrix, computed with dynamic programming rather than by running a separate search for every source.
The method is most revealing when the graph is weighted and may contain cycles. It handles positive, zero and negative edge weights, provided no negative-weight cycle makes the answer unbounded. It is especially useful when many distance queries are expected, because one matrix can replace many repeated single-source calculations. Understanding the recurrence, its update order and its limits gives programmers a dependable foundation for graph work beyond a copied implementation.
The shortest-path problem in graph form
A weighted graph can be written as (G=(V,E)), with a numerical weight attached to each edge. The weight might represent kilometres, travel minutes, cost or capacity. In a directed graph, an edge from (u) to (v) need not have a reverse edge; in an undirected graph, both directions share the same weight. A path is a sequence of vertices, and its length is the sum of its edge weights. The shortest path between two vertices is the path with the smallest finite length.
Floyd-Warshall stores tentative distances in a two-dimensional matrix. Initially, each entry contains the direct edge weight or infinity when no direct edge exists. The diagonal is zero because a vertex can reach itself without travelling. During the algorithm, the matrix changes to represent routes that use an increasing set of allowed intermediate vertices. The final matrix answers all source-destination queries in constant time.
Real networks often need that abstraction. A council in Sydney might represent roadworks as temporary edge-weight increases, while a logistics business in Melbourne might compare travel times to cafés, warehouses and depots. The exact measurements differ from ordinary mapping software, but the graph model remains the same. For wider programming context, the graph algorithm tutorials explain how graphs fit into common computer science tasks.
Dynamic programming across intermediate vertices
Let (D_k[i,j]) be the shortest distance from vertex (i) to vertex (j) when only the first (k) vertices may appear as intermediate stops. A shortest route either avoids vertex (k), or reaches (k) and then continues to (j). Therefore,
[ D_k[i,j] = \min\left(D_{k-1}[i,j],;D_{k-1}[i,k] + D_{k-1}[k,j]\right). ]
The two alternatives make this a dynamic-programming recurrence: the same subproblems feed the next stage.
Before processing any intermediate vertex, the matrix represents direct connections. Set (D[i,i]=0), set each existing edge weight in its corresponding cell, and leave every other cell at infinity. This base case handles missing routes and self-distance consistently. The recurrence then considers each vertex in turn as a possible junction, which is why Floyd-Warshall is also described as an intermediate-vertex relaxation.
Only one matrix is required in most implementations. For each (k), every entry is updated in place using the current values at row (k) and column (k). The outer loop must process intermediate vertices, while (i) and (j) can be traversed in either order. Once all vertices have served as junctions, the matrix no longer distinguishes between direct paths and routes through several intermediate vertices.
A small worked example
Consider an undirected graph with vertices A, B, C and D. Its edges are A–B with weight 4, A–C with weight 2, C–B with weight 1, B–D with weight 3 and C–D with weight 5. The direct A–B distance of 4 is not optimal, because travelling through C costs only 3. The route A–B–D costs 7, but A–C–B–D costs 6.
The initial matrix contains the five undirected edge weights in both directions, zeroes on the diagonal and infinity elsewhere. When B is considered, C–D becomes 4 through B and A–D becomes 7 through B. When C is then considered, A–B becomes 3 and the improved C–D route reduces A–D to 6. Although any order of intermediate vertices is valid, later vertices can build on improvements made through earlier ones.
The final distance matrix is:
| From/to | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 3 | 2 | 6 |
| B | 3 | 0 | 1 | 3 |
| C | 2 | 1 | 0 | 4 |
| D | 6 | 3 | 4 | 0 |
Reading row A gives the shortest distances from A: 3 to B, 2 to C and 6 to D. The matrix gives distances, not the routes themselves; a separate predecessor or next-hop matrix is needed when a program must reconstruct each path.
Why the update rule is correct
The recurrence is correct by induction over the allowed intermediate vertices. With no intermediates, a valid route can only be a direct edge or a zero-length path from a vertex to itself, exactly matching the initial matrix. When vertex (k) is added, an optimal route either does not use (k), retaining the previous distance, or uses (k) and splits into a route to (k) plus a route from (k). Taking the minimum of those two values covers every possibility.
Negative edge weights do not invalidate the argument. Floyd-Warshall can find shortest paths in a graph containing them, whereas Dijkstra's algorithm cannot safely handle negative edges. The essential restriction is the absence of a negative-weight cycle. If such a cycle exists, repeatedly traversing it lowers the total cost without bound, so no finite shortest distance exists for the affected vertices.
A negative diagonal entry after processing reveals this condition. Zero-weight cycles are harmless because traversing them changes neither cost nor reachability. A Boolean variant can replace addition with logical OR and minimum with logical OR to compute transitive closure: whether each vertex can reach each other. For ordinary weighted distances, however, the additive recurrence is the appropriate model.
A practical Python implementation
The following function accepts an adjacency matrix. A number is an edge weight, and None means that no direct edge exists.
def floyd_warshall(weights):
n = len(weights)
inf = float("inf")
dist = [[inf] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0.0
for i, row in enumerate(weights):
for j, weight in enumerate(row):
if weight is not None:
dist[i][j] = float(weight)
for k in range(n):
for i in range(n):
if dist[i][k] == inf:
continue
for j in range(n):
candidate = dist[i][k] + dist[k][j]
if candidate < dist[i][j]:
dist[i][j] = candidate
return dist
The k loop must remain outermost so that each vertex becomes an allowed intermediate exactly once. The i and j loops may run in either direction. Skipping an unreachable dist[i][k] avoids unnecessary arithmetic, while float("inf") propagates correctly when the second half of a candidate route is also unreachable.
For route reconstruction, maintain a next matrix alongside dist. Set next[i][j] = j for a direct edge. When the route through (k) is shorter, set next[i][j] = next[i][k], and following these pointers produces the path. This extra matrix uses (O(V^2)) space; a sparse graph with many vertices may instead justify repeated Dijkstra runs or a specialised library.
Practical guidance for graph projects
Floyd-Warshall takes (O(V^3)) time and (O(V^2)) space. That cubic cost suits a dense graph, a modest number of vertices or a service that expects many queries after one computation. For a sparse road network, one Dijkstra run from each source is often faster; Bellman-Ford is the standard single-source fallback when negative edges must be supported. Johnson’s algorithm is another all-pairs option when the graph is sparse and has negative edges but no negative cycles.
Australian use cases make the modelling choices concrete. Sydney and Melbourne road and public-transport networks contain many conditional links, including bridges, rail corridors, ferry legs and temporary closures. A courier serving a bakery, warehouse and café needs distances in kilometres and realistic journey times, rather than straight-line coordinates. Local councils, ride-hailing operators and small delivery businesses may all use such graphs, but each can assign different weights to congestion, load size and time windows.
Privacy needs attention when graph data can identify an individual. If records connect a person’s device or vehicle to a location, the Privacy Act 1988 and the Australian Privacy Principles may apply, so access controls and retention periods matter alongside algorithmic accuracy. For Python services that serve live route requests, the asynchronous Python workflows guide explains how event-loop concurrency can keep network work from blocking. The matrix calculation remains CPU-bound, so it should not be mistaken for an asynchronous optimisation.
Before choosing an approach, consider these practical recommendations:
- Confirm that the edge weights express the quantity being optimised, including units and direction.
- Normalise the graph size and sparsity against the cubic time cost.
- Decide whether distance values alone are sufficient or route reconstruction is required.
- Test diagonal entries, disconnected vertices and unreachable routes.
- Include a negative-cycle check whenever negative weights are permitted.
- Benchmark the complete workload, including query frequency and memory limits.
With the correct graph model, Floyd-Warshall provides a compact, transparent all-pairs result whose intermediate steps are easy to inspect, test and explain.