A distance matrix D extends an adjacency matrix: entry D[i][j] records the distance from point i to point j. Because argument order matters, D[i][j] may differ from D[j][i]. section 6.1.5
Representing absent connections
For a graph G, store the distance between every pair of points in D. Represent the absence of a direct arc with a very large value such as SIZE_MAX; use the matrix to seek a shortest path between input nodes x and y. section 6.1.5
TAKEAWAY
- Treat each ordered pair as a matrix entry. section 6.1.5
- Use a sentinel value such as SIZE_MAX when no direct arc exists. section 6.1.5
