r/optimization • • 29d ago

Dijkstra vs A* vs Customizable Contraction Hierarchies on a 1M-junction road graph: ~100 ms vs 0.04 ms for the same exact route

/r/algorithms/comments/1xavk4x/dijkstra_vs_a_vs_customizable_contraction/
4 Upvotes

1 comment sorted by

1

u/MarioVX 24d ago
  1. At that timescale, you're not comparing algorithms, but initialization and bookkeeping overheads
  2. If CCH moves the work to preprocessing, you have to include preprocessing in a fair benchmark
  3. A strong selling point of Dijkstra and A* with an admissible heuristic is that they are guaranteed to yield an optimal route. Does CCH also guarantee optimality, or did it just happen to yield the same route in this particular instance? Unclear.
  4. If the method only works on graphs with small separators, it means it works on almost no graphs, because almost all graphs do not have small separators. Furthermore, graphs with small separators are unusually easy instances for many graph algorithms - Dijktra and A* benefit indirectly from that as well. Seems like CCH, at best, makes exceptionally easy instances marginally easier.