# single source shortest path

Dijkstra’s Algorithm

- does not work if graph has negative edge weights

Bellman-Ford-Moore

- https://en.wikipedia.org/wiki/Shortest_path_faster_algorithm
- use a queue to store nodes where we found a shorter path
- pop node off the queue and relax adjacent nodes
- same worst case as standard Bellman-Ford, but O(E) on average for random graphs
- negative cycle detection
- walk to the root
- subtree disassembly

Randomized Speedup of the BellmanāFord Algorithm

- mn/3 + m relaxation steps in expectation

Goal directed or point to point SP

- A* landmarks and triangle inequality (ALT)