(classic problem)
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.
Author: PEB
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
