(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 Mon May 16 10:46:53 2005.
HTML page formatted Wed Oct 26 09:48:08 2005.
Cite this as:
Paul E. Black, "shortest path", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/shortestpath.html
