Graph Distance


The distance d(u,v) between two vertices u and v of a finite graph is the minimum length of the paths connecting them (i.e., the length of a graph geodesic). If no such path exists (i.e., if the vertices lie in different connected components), then the distance is set equal to infty. In a grid graph the distance between two vertices is the sum of the "vertical" and the "horizontal" distances (right figure above).

The matrix (d_(ij)) consisting of all distances from vertex v_i to vertex v_j is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix.

See also

All-Pairs Shortest Path, Bellman-Ford Algorithm, Floyd-Warshall Algorithm, Dijkstra's Algorithm, Distance Graph, Girth, Graph Circumference, Graph Diameter, Graph Distance Matrix, Graph Geodesic, Shortest Path Problem

This entry contributed by Margherita Barile

Explore with Wolfram|Alpha


Buckley, F. and Harary, F. Distance in Graphs. Redwood City, CA: Addison-Wesley, 1990.Diestel, R. Graph Theory, 3rd ed. New York: Springer-Verlag, p. 8, 1997.Wilson, R. J. Introduction to Graph Theory, 3rd ed. New York: Longman, p. 30, 1985.

Referenced on Wolfram|Alpha

Graph Distance

Cite this as:

Barile, Margherita. "Graph Distance." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications