# 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*, *k*^{th} 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