Melvin's digital garden

single source shortest path

Dijkstra’s Algorithm

  • does not work if graph has negative edge weights


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)

A Survey of Shortest-Path Algorithms

Links to this note