The graph distance matrix, sometimes also called the all-pairs shortest path matrix, is the square matrix 
consisting of all graph
distances from vertex 
to vertex 
. The distance matrix for graphs was introduced by Graham
and Pollak (1971).
The mean of all distances in a (connected) graph is known as the graph's mean distance. The maximum value of all distance matrix elements is known as the graph diameter.
The characteristic polynomial of the graph distance matrix is known as the distance polynomial.
The graph distance matrix can be computed in the Wolfram Language using the built-in function GraphDistanceMatrix[g], and precomputed distance matrices for many named graphs can be obtained using GraphData[graph, "DistanceMatrix"].
For a connected graph on 
vertices, the linear system of equations
 |
(1) |
where 
is the distance matrix and 
is the vector consisting of 
1's, tends to have a real solution for "most" graphs
(Steinerberger 2022, Chen and Tsui 2025). Exceptions include the complete 
-partite graphs 
and 
, the "double pac-man graph," the 
knight
graph, and the 14-node cubic graph #52 and 11-node
quartic graph #18 (in the numbering of GraphData).
The numbers of connected graphs with no solution
to the above equation on 
, 2, ... nodes are 1, 0, 0, 0, 0, 0, 2, 14, 398, 23923, ...
(OEIS A354465). Dudarov et al. (2023)
proved that such graphs exist for all 
.
The first few "ones vector not in distance matrix image graphs" that are also k-trees (which occurs for 
, 7, and 8 nodes) are illustrated above. The 8-node graphs
#1 and 2 are 2-trees, while the 8-node graph #13 is a
4-tree (E. Weisstein, Jan. 18, 2024).
The real eigenvector 
with nonnegative entries associated with the largest eigenvalue
(as guaranteed to exist by the Perron-Frobenius
theorem) is nearly constant in the sense that the inner
product satisfies
 |
(2) |
where 
is the 
-norm
(Steinerberger 2022). However, the Perron-Frobenius eigenvectors for the distance
matrices of the thousands of connected graphs in GraphData
give an average value for 
that is close to 
as opposed to 
. The conditions under which this may
be true is apparently an open problem, as noted by Steinerberger (2023). However,
exact values for limiting cases of certain families are known, e.g.,
 |
(3) |
for the path graph 
, where 
is the positive root of 
(Ruzieh and Powers 1990, Steinerberger 2023), and
 |
(4) |
for the sun graph 
(Steinerberger 2023). These considerations are related to
the definition of graph curvatures.
See also
All-Pairs Shortest Path, Antipodal Graph, Bellman-Ford Algorithm, Detour Matrix, Dijkstra's Algorithm, Distance Polynomial, Floyd-Warshall Algorithm, Geodetic Graph, Graph Diameter, Graph Distance, Graph Geodesic, Harary Index, Longest Path, Mean Distance, Shortest Path, Shortest Path Problem
Explore with Wolfram|Alpha
References
Aouchiche, M. and Hansen, P. "Distance Spectra of Graphs: A Survey." Linear Algebra Appl. 458, 301-386, 2014.Balaji,
R. and Bapat, R. B. "On Euclidean Distance Matrices." Linear Algebra
Appl. 424< 108-117, 2007.Bapat, R. B. Ch. 3
in Graphs and Matrices. New Delhi, India: Springer, 2010.Chen,
W. C. and Tsui, M.-P. "On Steinerberger Curvature and Graph Distance Matrices."
Disc. Math. 348, 114475, 2025.Devillers, J. and Balaban,
A. T. (Eds.). Topological
Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands:
Gordon and Breach, pp. 76-80, 2000.Dudarov, W.; Feinberg, N.; Guo,
R.; Goh, A.; Ottolini, A.; Stepin, A.; Tripathi, R.; and Zhang, J. "On the Image
of Graph Distance Matrices." 10 Jul 2023. https://arxiv.org/abs/2307.04740.Graham,
R. L.; and Pollak, H O. "On the Addressing Problem for Loop Switching."
Bell Syst. Tech. J. 50, 2495-2519, 1971.Hakimi, S. L.;
and Yau, S. S. "Distance Matrix of a Graph and Its Realizability."
Quart. J. Appl. Math. 22, 305-317, 1965.Ruzieh, S. and
Powers, D. L. "The Distance Spectrum of the Path 
and the First Distance Eigenvector of Connected Graphs."
Linear Multilinear Algebra 28, 75-81, 1990.Sloane, N. J. A.
Sequence A354465 in "The On-Line Encyclopedia
of Integer Sequences."Steinerberger, S. "The First Eigenvector
of a Distance Matrix Is Nearly Constant." Disc. Math. 346, 113291,
2023.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Graph Distance Matrix." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphDistanceMatrix.html