Melvin's digital garden

single source shortest path

Dijkstra’s Algorithm

  • does not work if graph has negative edge weights


  • 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)

A Survey of Shortest-Path Algorithms

Links to this note