Single-source shortest paths
12 methods in the atlas attack this one problem. They are rivals: each wins something the others do not.
Phrasings that mean this problem
Nonnegative shortest pathsNegative-edge shortest pathsBinary-weight shortest pathsSmall-weight shortest pathsParallel shortest pathsPoint-to-point shortest pathsUnweighted shortest reachPractical Bellman-FordLinear-time undirected SSSP theoryAcyclic-graph pathsPoint-to-point search
graphs-paths
- Breadth-first searchstandalonecanongraphs-paths
- 0-1 BFSDeque front-back relaxationstandardgraphs-paths
- Dijkstra's algorithmBinary heap priority queuecanonfull lesson ▸graphs-paths
- Bidirectional DijkstraBalanced frontier terminationstandardgraphs-paths
- Dial's algorithmBucket-indexed distancesspecialistgraphs-paths
- Bellman-FordEarly-exit relaxationcanonfull lesson ▸graphs-paths
- SPFASmall-label-first queueingspecialistgraphs-paths
- SPFALarge-label-last queueingspecialistgraphs-paths
- Delta-steppingBucketed light-heavy relaxationspecialistgraphs-paths
- Thorup's algorithmstandalonespecialistgraphs-paths
- Bidirectional A*Consistent-heuristic meeting rulespecialistgraphs-paths
- DAG shortest pathTopological-order relaxationstandardgraphs-paths