All-Pairs Shortest Path

The all-pairs shortest path problem is the determination of the shortest graph distances between every pair of vertices in a given graph. The problem can be solved using n applications of Dijkstra's algorithm or all at once using the Floyd-Warshall algorithm. The latter algorithm also works in the case of a weighted graph where the edges have negative weights.

The matrix of all distances between pairs of vertices is called the graph distance matrix, or sometimes the all-pairs shortest path matrix.

The graph distance matrix of a graph g can be found in the Wolfram Language using GraphDistanceMatrix[g], and a shortest path between two vertices u and v using FindShortestPath[g, u, v].

See also

Bellman-Ford Algorithm, Dijkstra's Algorithm, Floyd-Warshall Algorithm, Graph Distance, Graph Distance Matrix, Graph Geodesic, Shortest Path Problem

Explore with Wolfram|Alpha


Pemmaraju, S. and Skiena, S. "All-Pairs Shortest Paths." §8.1.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, pp. 330-331, 2003.Skiena, S. "All Pairs Shortest Paths." §6.1.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 228-229, 1990.

Referenced on Wolfram|Alpha

All-Pairs Shortest Path

Cite this as:

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

Subject classifications