(classic problem)

**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. *

* After LK.*

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

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