Download Wolfram Notebook

A graph geodesic is a shortest path between two graph vertices of a graph (Skiena 1990, p. 225). There may be more than one different shortest paths, all of the same length. Graph geodesics may be found using a breadth-first traversal (Moore 1959) or using Dijkstra's algorithm (Skiena 1990, p. 225). One (of possibly several) graph geodesics of a graph from vertex to vertex can be found in the Wolfram Language using FindShortestPath[g, u, v]. The length of the graph geodesic between these points is called the graph distance between and .

The length of the maximum geodesic in a given graph is called the graph diameter, and the length of the minimum geodesic is called the graph radius.

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

A graph which possesses a unique geodesic between every pair of vertices is known as a geodetic graph.

See also

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

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 14, 1994.Moore, E. F. "The Shortest Path through a Maze." In Proc. Internat. Symp. Switching Th., Part II. Cambridge, MA: Harvard University Press, pp. 285-292, 1959.Skiena, S. "Shortest Paths." §6.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 225-253, 1990.

Referenced on Wolfram|Alpha

Graph Geodesic

Cite this as:

Weisstein, Eric W. "Graph Geodesic." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphGeodesic.html

Subject classifications