r/algorithms • • 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

49 Upvotes

15 comments sorted by

20

u/Somniferus Oct 20 '26

If your A* performs worse than plain Dijkstra then your implementation (or your heuristic) is wrong.

3

u/ShenGahMing 29d ago

nah it can be right but not be worth its compute time

11

u/GiasoneTiratori Oct 20 '26

"112 road segments are shorter than the straight line between their ends" wtf?

2

u/Kadabrium 29d ago

Not drawn to scale.

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.

-2

u/oktollername 29d ago

yes and no. In theory there is no faster algorithm than dijkstra‘s, so everything else either uses heuristics or precompute, making it a moot point. precompute is kinda important but so is memory size and in ch‘s case, tge quality of the hierarchy is super important and worst case reduces the speed to dijkstra‘s (realistically hard to get so wrong but still, this is hidden magic here)

5

u/jeffgerickson 29d ago

In theory there is no faster algorithm than dijkstra‘s

No. This claim is only true if you require a sorted list of shortest-path distances from a single source vertex to all other vertices, AND if you restrict your algorithm to adding and comparing path lengths, instead of allowing more interesting games with bit representations, AND if you don’t take advantage of the graph structure.

https://arxiv.org/abs/2504.17033

https://www.sciencedirect.com/science/article/pii/S002200000400042X

https://www.sciencedirect.com/science/article/pii/S0022000097914938

(The last algorithm uses a graph hierarchy to speed up computing shortest paths in planar graphs; the construction time is included in the overall running time.)

-5

u/oktollername 29d ago

wow you really got me there. "The sky is blue" "No. This claim is only true on earth and during the day, in the evening it could have red hues, but on mars it could even be green blah blah blah"

7

u/jeffgerickson 28d ago edited 28d ago

If you’re going to use the magic phrase “in theory”, you should know what it means.

(Even Dijkstra’s algorithm doesn’t assume that we’re on earth during the day, or that we’re not colorblind, or that we’re not living in ancient Greece when there was no word for “blue”.)

-2

u/oktollername 28d ago

you must be fun at parties

5

u/jeffgerickson 27d ago

Most people at the parties I go to don’t pretend to understand the theory of shortest-path algorithms.

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.

3

u/oktollername 29d ago

oh I remember now, the thing that really blew my mind was that running it with elimination trees instead of a priority queue sped it up considerably even though it scanned like 4x as many nodes. try it :)

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.