Definition: The problem of finding the shortest path in a graph from one vertex to another. "Shortest" may be least number of edges, least total weight, etc.
Also known as single-pair shortest-path problem.
See also Dijkstra's algorithm, Bellman-Ford algorithm, DAG shortest paths, all pairs shortest path, single-source shortest-path problem, kth shortest path.
Note: The problem is to find the weight of the shortest path. For a map, it is to produce the (shortest) road distance from one city to another city, not which roads to take.
A modification to most algorithms finds the shortest path, too. In predecessor[i][j] save the immediate predecessor of the shortest path from i to j. Suppose predecessor[i][j] is k; then the shortest path ends with ... → k → j. If predecessor[i][k] is p, the shortest path ends with ... → p → k → j. Continue working backward until you reach i.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 16 May 2005.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "shortest path", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 May 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/shortestpath.html