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 Mon Nov 18 10:44:09 2013.
Cite this as:
Paul E. Black, "all pairs shortest path", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 1 February 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/allPairsShortestPath.html