NIST

shortest path

(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

Implementation

(C, C++, Pascal, Fortran, and Mathematica)
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 September 2014.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "shortest path", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/shortestpath.html