Is A* Always Faster Than Dijkstra? When to Consider CCH
In ArcadeDB's Florida road test, Dijkstra found the route in 99 ms and A* took 121 ms. Why was the smarter search slower, and when does CCH pay off?
- A* only benefits when its estimate reduces enough search work.
- CCH separates topology preprocessing, weight customization and queries.
- Query frequency and graph structure matter alongside latency.
A destination estimate does not guarantee a faster search
Replacing Dijkstra with A* can make a route query slower. In ArcadeDB’s October 13 comparison, a route across Florida took 99 ms with Dijkstra and 121 ms with A*. CCH answered it in 0.039 ms.
Those are the vendor’s medians of three runs on an Apple M5 Pro, using the same in-memory graph. The CCH figure comes with preparation costs: 6.6 seconds for the hierarchy and 306 MB for the view plus hierarchy. A request’s latency is only one part of the trade.
An aggressive estimate can change the answer
A* prioritizes candidates using the cost so far plus an estimate of the remaining cost. NetworkX’s API documentation warns that an estimate exceeding the true remaining cost can produce a path that is not shortest.
First decide what the weight represents. Distance and travel time require different estimates; adding a distance directly to elapsed time mixes units. When the estimate provides little guidance, its computation can add work without removing enough exploration. Compare the returned route cost as well as elapsed time when tuning it.
Preprocessing need not freeze traffic costs
Customizable Contraction Hierarchies rank vertices and introduce shortcuts that preserve routes. Queries then explore a restricted hierarchy. The paper by Dibbelt, Strasser and Wagner separates expensive topology preprocessing from cheaper weight customization and subsequent queries.
That separation supports changing travel costs on an existing network. The paper also describes game maps where buildings and unit types affect movement. Preprocessing does not mean that every edge must keep the same cost forever.
ArcadeDB provides CCH from version 26.10.2. Its routing documentation says a query falls back to Dijkstra when a suitable, current hierarchy is unavailable. Calling the CCH function therefore does not prove that the hierarchy answered.
Match the method to the answer you need
| Workload | Starting point |
|---|---|
| Fewest edges, without weights | Breadth-first shortest-path search. |
| Occasional routes with nonnegative costs | Dijkstra. |
| A useful lower-bound estimate to the destination | A*, measuring the net benefit. |
| Repeated routes on a road-like network | CCH, including preparation and updates. |
| Distances from one source to every vertex | Single-source Dijkstra. |
A social graph dominated by highly connected vertices is a different proposition from a road network. ArcadeDB can mark an oversized hierarchy candidate UNSUITABLE and retain Dijkstra. Inspect status and fallbacks when investigating unexpected latency.
For an adoption test, preserve your actual route distribution and update frequency. A* is a bet on useful guidance during search; CCH is a bet on reusing preparation across requests. Measure the work each approach removes and the work it adds.