Graph Geodesic

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A shortest path between two graph vertices (u,v) 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 g from vertex u to vertex v can be found in the Wolfram Language using FindShortestPath [g, u, v]. The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v.

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 (d_(ij)) consisting of all graph 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.

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