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 E. Black.
Entry modified 1 February 2005.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "all pairs shortest path", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 1 February 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/allPairsShortestPath.html