liveBook · Manning

Distance matrix

As explained in Algorithms Every Programmer Should Know

A distance matrix is a square matrix whose entries represent distances between pairs of vertices or locations.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines matrix initialization, traces a route update, and notes in-place storage, without deriving the algorithm formally.
Examples
Uses a four-vertex directed graph and updates the distance from vertex 4 to vertex 2 to 4 via vertex 1.
What it assumes
Uses vertices and edge weights, while defining how to represent direct edges, missing paths, and self-distances.
What you can do after
Apply Floyd–Warshall to compute all-pairs distances and identify negative-weight cycles from the completed matrix.
How it connects
Connects distance matrices to graphs, adjacency matrices, Floyd–Warshall, shortest paths, and negative-cycle detection.

Also explained in

Compare how 4 books explain distance matrix →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.