Shortest Path

A shortest path between two vertices of a graph is a graph path of shortest possible length between them. Such paths are also known as graph geodesics, and the matrix giving the lengths of shortest paths between all pairs of vertices in a graph is known as a graph distance matrix.

The problem of finding a shortest path in a graph is known as the shortest path problem.

See also

All-Pairs Shortest Path, Antipodal Graph, Graph Distance Matrix, Graph Geodesic, Shortest Path Problem

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Shortest Path." From MathWorld--A Wolfram Web Resource.

Subject classifications