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