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 15 July 2019.
HTML page formatted Mon Jul 15 12:55:43 2019.

Cite this as:
Paul E. Black, "shortest path", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 15 July 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/shortestpath.html