In graph theory [Graph theory], the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

## Algorithms

- Single-source shortest path problem
- Non-negative weights: Dijkstra’s algorithm, A*
- Negative weights: Bellman-Ford algorithm

- Single-pair shortest path problem
- Non-negative weights: Dijkstra’s algorithm
- Negative weights: Bellman-Ford algorithm

- All-pairs shortest path problem

## Backlinks

- Single-pair shortest path problem
- All-pairs shortest path problem
- Widest path problem
- Directed acyclic graph
- Single-source shortest path problem
- December 2022
- Dijkstra’s algorithm
- Ali Kemal Sinop, Lisa Fawcett, Sreenivas Gollapudi, Kostas Kollias | Robust Routing Using Electrical Flows
- Todos
- Contraction hierarchies