A distance matrix is a square table of distances between pairs of vertices. Rows mark starting vertices; columns mark destinations. For Floyd–Warshall, initialize direct edges with their weights, missing connections with infinity, and each diagonal entry with zero. section 9.1
Figure 9.1 The initial state of the network. The left panel shows the directed, weighted graph. The right panel shows the baseline distance matrix (A0). Existing direct paths are recorded with their cost, while missing connections are initialized to infinity (∞). The diagonal is zero, as the distance from any node to itself is zero.
See the directed graph beside its initial matrix, with edge costs, missing paths, and zero-valued diagonal entries. section 9.1
Floyd–Warshall updates the matrix as it tests each vertex as an intermediate stop. For each start and destination, it compares the known distance with the cost of traveling through the tested vertex, keeping the smaller value. The completed matrix gives shortest distances for every pair. section 9.1 section 9.4
A detour makes a connection
In the four-vertex example, there is no direct route from vertex 4 to vertex 2, so the initial entry is infinity. Testing vertex 1 finds a route costing 2 + 2 = 4; the matrix entry is updated to 4. section 9.1
The matrix also supports practical tradeoffs and checks:
- Precomputing all pairs costs O(V³), but makes later distance lookups O(1); this tradeoff suits dense graphs better than sparse ones. section 9.4
- A negative diagonal entry after execution signals a negative-weight cycle. section 9.4



