Graph Distance

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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 Graph, Graph Distance Matrix, Graph Geodesic, Shortest Path Problem

This entry contributed by Margherita Barile

Explore with Wolfram|Alpha

References

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 Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/GraphDistance.html

Subject classifications