# 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 2 September 2014.

HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:

Paul E. Black, "shortest path", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 2 September 2014. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/shortestpath.html