Definition: Find the weight (or length) of the shortest paths between all pairs of vertices in a weighted, directed graph.
See also Floyd-Warshall algorithm, Johnson's algorithm similar problems: single-source shortest-path problem, shortest path, minimum spanning tree, traveling salesman, all simple paths.
Note: The problem is to find the weights of the shortest paths between all pairs of vertices. For a map, it is to produce the (shortest) road distances between all cities, not which roads to take to get from one city to another.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 1 February 2005.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "all pairs shortest path", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 1 February 2005. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/allPairsShortestPath.html