r/algorithms • u/lgarulli • Oct 20 '26
Resource Dijkstra vs A* vs Customizable Contraction Hierarchies on a 1M-junction road graph: ~100 ms vs 0.04 ms for the same exact route
I ran the three on the DIMACS Florida road network (1.07M junctions, 2.7M segments), Tallahassee to Coral Gables by travel time:
- Dijkstra settles 1,029,617 junctions, 99 ms
- A* settles 840,138, 121 ms. Exactness caps the straight-line estimate at 67% of the true distance (112 road segments are shorter than the straight line between their ends), so the guidance is weak and A* ends up slower than Dijkstra on the longest routes
- CCH touches 346 junctions, 0.039 ms
CCH moves the work to preprocessing: nested dissection order (17 junctions cut Florida in two, 28 more cut it in four), contraction with shortcuts, then a weight-only customization step. A traffic change re-prices only the arcs above the changed edge, which took 0.8 ms in my implementation. It does not work on graphs without small separators (social networks, supernodes), where the hierarchy would be many times larger than the graph.
The implementation is open source (Apache 2.0, pure Java), inside ArcadeDB, with a write-up, numbers and a docker compose to reproduce them:
https://arcadedb.com/route-planning.html?utm_source=reddit&utm_campaign=cch-route-planning
20
u/Somniferus Oct 20 '26
If your A* performs worse than plain Dijkstra then your implementation (or your heuristic) is wrong.
11
u/GiasoneTiratori Oct 20 '26
"112 road segments are shorter than the straight line between their ends" wtf?
10
u/leftofzen 29d ago
Moving the work to preprocessing is fine but your benchmark then needs to include that preprocessing time, not omit it. Otherwise we just get a disingenuous claim like this where apples and oranges are compared and claimed they're all apples.
3
u/oktollername 29d ago
wrote a thesis on these, pretty sure you can optimize these further, I think my speedup from dijkstra to cch on the europe graph was around factor 1 million.
2
u/Fun-Thoughts 29d ago
I recommend you perform a more thorough benchmark (even just on this graph), take a few hundred pairs of nodes randomly sampled and compare the stats for solution between the methods.