Contraction Hierarchies Find a Florida Route by Settling 346 Junctions Instead of a Million
Dijkstra vs. A* vs. Contraction Hierarchies
ArcadeDB benchmarks Dijkstra, A*, and Customizable Contraction Hierarchies on Florida's real road network: 1.07 million junctions, 2.7 million segments. For a Tallahassee-to-Coral Gables trip, Dijkstra settles 1,029,617 junctions, A* 840,138, and CCH just 346, returning the same 8-hour-18-minute route in 0.039 ms versus 99 and 121 ms. The hierarchy lives inside the database, so a traffic jam is an ordinary property update that re-prices only the affected arcs.
That is the difference between a routing feature of the database and a routing cache next to it: there is no window in which a query returns a route over a road that was closed a second ago.