The classic answers to "what is the fastest way from A to B?", Dijkstra and A*, are exact and need no preparation, but the farther apart the two points, the more of the network they read. The animation runs them and a Customizable Contraction Hierarchy on the real road network of Florida, 1.07 million junctions and 2.7 million road segments, from Tallahassee to Coral Gables by travel time: 8 hours 18 minutes, down I-75 and the Florida Turnpike. Each colored square is a part of the state the search has to read before it knows the answer, and all three panels play at the same speed. All three return the same route, to the second.
Dijkstra: 1,029,617 junctions
Settles junctions in order of travel time from the start. Its search is a growing circle: by the time it reaches Coral Gables it has settled almost all of Florida, because Pensacola, Jacksonville and Tampa are closer to Tallahassee than Coral Gables is. No preparation, works on any graph with non-negative weights.
A*: 840,138 junctions
Adds an estimate of the time left from the straight line to Coral Gables and leans the circle south. To stay exact the estimate may never exceed a real road, and a few of Florida's 2.7 million segments are faster than the straight line suggests, so the guidance is weak and the search still covers most of the state. Needs coordinates on the vertices.
CCH: 346 junctions
Climbs a precomputed hierarchy from both ends until the two climbs meet: 166 junctions above Tallahassee, 163 above Coral Gables. The work barely depends on the distance, so the gap is three orders of magnitude: 0.04 ms instead of about 100. Exact, not a heuristic.
How Customizable Contraction Hierarchies Work
The technique, from the research of Dibbelt, Strasser and Wagner, moves the work from query time to preparation time, and splits the preparation into a part that depends only on which roads exist and a part that depends on what they cost. That split is what lets the hierarchy follow traffic.
Order, Contract, Customize, Query
- Order (once): find a small set of junctions that cuts the network in two (in Florida, 17 junctions cut the state in two, 28 more cut it in four), then recurse into each half. Road networks are full of small separators: bridges, passes, the few junctions every long route crosses.
- Contract (once): remove the junctions bottom-up, adding a shortcut wherever a removal would break a route. No weights are needed yet.
- Customize (on every weight change): price every road and shortcut from the weights. After a change, only the arcs above the changed road are re-priced.
- Query (on every request): walk up from both endpoints, meet, unpack the shortcuts into real roads. No priority queue, no frontier, a few kilobytes of scratch.
ArcadeDB keeps the hierarchy on a Graph Analytical View, the in-memory columnar copy of the graph its analytics run on, and keeps it in step with every commit.
One Statement to Enable It
-- one hierarchy per cost: distance and time
CREATE GRAPH ANALYTICAL VIEW Florida
EDGE TYPES (ROAD)
UPDATE MODE SYNCHRONOUS
CCH (km, minutes)
Built in the background, about 7 seconds for the 2.7 million roads of Florida. Queries never wait for it.
The Same Route, in Cypher and SQL
// Cypher: route and total travel time
MATCH (a:Junction {name: 'Tallahassee'}),
(b:Junction {name: 'Coral Gables'})
CALL algo.cch.shortestPath(a, b,
'ROAD', 'minutes', 'OUT')
YIELD path, weight
RETURN weight AS minutes, size(path.nodes) AS junctions
-- SQL: the junctions of the route, in order
SELECT lat, lon FROM (
SELECT expand(cchShortestPath($from, $to, 'minutes',
{ direction: 'OUT', edgeTypeNames: ['ROAD'] }))
LET $from = (SELECT FROM Junction WHERE name = 'Tallahassee'),
$to = (SELECT FROM Junction WHERE name = 'Coral Gables')
)
dijkstra() and astar() take the same arguments, so switching algorithm is one word.
Always Exact, Never Stale
cchShortestPath() and algo.cch.shortestPath always return the exact shortest path and pick the fastest way to compute it. The hierarchy answers when it was prepared for exactly the data the view is serving. Otherwise the same call answers with bidirectional Dijkstra: while the hierarchy is being built or is catching up with a commit, for a different weight, or for a transaction that holds uncommitted changes, which it sees as part of the route.
Only the speed changes, never the answer. 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.
Every hierarchy reports its status, size and memory, the queries it answered and the ones it handed to Dijkstra, and how long the last update took from commit to ready, through SELECT FROM schema:graphAnalyticalViews. In Cypher, PROFILE says when a query was answered by the hierarchy.
Live Traffic: One UPDATE, a New Route a Millisecond Later
A weight is an ordinary edge property. Traffic feeds, closures and maintenance windows are plain UPDATE or Cypher SET statements, in a transaction, next to the rest of your data. The hierarchy re-prices only the arcs above the changed road and keeps everything else.
Weights Change Every Second, the Hierarchy Keeps Up
Measured on the Florida road network, from the commit until the hierarchy answers for the new data (median of three runs):
| Change |
Commit + catch-up |
| 1 road weight | 0.61 + 0.19 ms |
| 10 road weights | 5.0 + 3.3 ms |
| 100 road weights | 34 + 7.2 ms |
| Close a road | 0.81 + 0.14 ms |
| A new road between junctions not yet joined | 0.46 s |
A road is closed by giving it a negative weight, which no path finder walks, and reopened by restoring it. A new road keeps the existing order and only re-contracts.
Traffic Is Just a Property Update
// four hours of queue on the Turnpike
MATCH (:Junction {id: 702459})
-[r:ROAD]->(:Junction {id: 702911})
SET r.minutes = 240
-- the same road closed, in SQL:
-- a negative weight is never walked
UPDATE ROAD SET minutes = -1
WHERE @rid = :road
Tallahassee to Coral Gables leaves I-75 and the Turnpike (8 h 18 min) for I-10 and I-95 down the Atlantic coast (8 h 20 min). The hierarchy caught up in 0.9 ms.
Tallahassee to Coral Gables
| Minimize |
Route |
Cost |
km |
Highways through the interior, past Lake Okeechobee |
742 km, 11 h 19 min |
minutes |
I-10, I-75, the Turnpike |
789 km, 8 h 18 min |
Same query, same view, a different weight property: 46 km longer, 3 hours faster.
Several Costs on One Network
The shortest route is rarely the only one that matters. Distance, travel time, tolls, fuel, emissions, risk: each is a property on the same edges, and a view keeps one hierarchy per cost, all built from the same topology and all kept up to date by the same commits.
Because the network lives in a multi-model database, the costs can come from anywhere in it: travel times aggregated from time-series sensor data, tolls stored as documents, restrictions joined from your asset records. The route is computed where the data already is.
Benchmark: CCH vs Dijkstra vs A* on 1 Million Junctions
The DIMACS Florida road graph (USA-road-d.FLA) has 1,070,376 junctions and 2,712,798 road segments. The routes start in Tallahassee and go to 12 destinations, from the nearest to the farthest quantile of its shortest-path tree, plus Coral Gables, across the state.
Dijkstra pays for every kilometer, CCH does not: its line is flat. Per query it also allocates kilobytes instead of tens of megabytes, which is what lets one server answer many routing requests in parallel without feeding the garbage collector.
A* is only as good as its estimate. To stay exact, the straight line to the destination may never exceed the real cost of any road, and in this data 112 of 2.7 million road segments are shorter than the straight line between their ends. That caps the estimate at 67% of the true distance. A* is then 2.5x faster than Dijkstra for nearby destinations, and slower across the state, where the weaker estimate no longer pays for its extra work. A bolder estimate would be faster and could return a longer route. CCH has no estimate to tune.
CCH pays once, up front: seven seconds to build the hierarchy for Florida and memory to hold it. For a network that serves many queries, that trade is easy. All numbers are the median of three runs of CCHRoadNetworkBenchmark in the open source engine, which runs on any DIMACS road graph; more results on our benchmarks page.
Florida, Apple M5 Pro
|
CCH |
Dijkstra |
A* |
| Query, near to farthest | 0.010-0.041 ms | 7.8-104 ms | 3.1-132 ms |
| Tallahassee to Coral Gables | 0.039 ms | 99 ms | 121 ms |
| CCH speed-up vs Dijkstra | 780-3,100x | | |
| Memory per query | 6-43 KB | 11-44 MB | 9-52 MB |
| Through the database | 0.04-0.06 ms | | |
| First build | 6.6 s | none | none |
| Memory, view + hierarchy | 306 MB | none | none |
Which Path Finder, When
| You need |
Use |
| The fewest hops | shortestPath() |
| A weighted route, now and then | dijkstra(), algo.dijkstra |
| The same, with coordinates | astar(), algo.astar |
| Many routes on a road-like network | cchShortestPath(), algo.cch.shortestPath |
| Alternatives | algo.kShortestPaths |
| Negative weights | bellmanFord() |
| Distances to every destination | algo.dijkstra.singleSource |
When Not to Use Contraction Hierarchies
CCH is a tool for networks with geography (roads, rail, pipes, power lines, floor plans, game maps) that answer many point-to-point queries. Reach for something else when:
- The graph has no small separators. Social networks, citation graphs, anything with supernodes would need a hierarchy many times larger than the graph. ArcadeDB detects it, marks the hierarchy
UNSUITABLE and keeps answering with Dijkstra.
- You ask rarely. For a handful of routes a day, Dijkstra or A* need no preparation and no memory.
- Weights can be negative. Use Bellman-Ford.
- You need every destination from one source, as in a delivery-area map. Use single-source Dijkstra.
- You need turn-by-turn navigation on public maps. Dedicated engines built on OpenStreetMap, with turn costs and road profiles, are the right tool. ArcadeDB is for routing over your network and your data.
Route Planning Applications
Logistics & Delivery
Depots, hubs and customer sites on one network. Price every candidate leg of a dispatch plan in microseconds, by distance, time or cost, and re-plan as soon as a road closes. Pairs naturally with the supply chain graph the shipments already live in.
Fleet & Field Service
Find the technician who can reach a failed asset first, with the travel times your telematics reported a minute ago, and the skills and spare parts stored next to them in the same database.
Utility & Telecom Networks
Power grids, water mains, gas pipelines, fiber: route around a failure, find the lowest-loss or lowest-latency path, and see the effect of switching a segment off before doing it.
Warehouses & Indoor Navigation
Aisles, floors, elevators and gates of a warehouse, hospital, airport or campus. Picking paths and wayfinding that follow blocked aisles and crowded corridors as they happen.
Mobility & Transport
Rail, ferry and road links with travel times, tolls and emissions as separate costs on the same edges. Answer "fastest", "cheapest" and "greenest" from one network.
Games & Simulation
Large world maps where many agents route at once and the terrain changes. Microsecond queries with a few kilobytes of scratch each, embedded in the game server's JVM.
Why ArcadeDB for Route Planning
Contraction hierarchies are well studied. Making them behave like a database feature is the hard part:
- In the database: no export, no preprocessing job, no routing service to keep in sync. The network, its weights and the hierarchy share one engine and one transaction log.
- Exact under change: a query is answered by the hierarchy only for exactly the data it was prepared for, and by bidirectional Dijkstra otherwise. A transaction sees its own uncommitted changes.
- Incremental: weight changes, closures and deletions re-customize only the arcs above them; new roads keep the existing order.
- Several costs:
CCH (km, minutes, toll), built and kept up to date together.
- Persisted: the expensive part, the order, is saved at a clean close and reused on restart.
- Safe on the wrong graph: graphs without small separators are detected and refused instead of exhausting the heap.
- Light: primitive arrays throughout, a per-query scratch sized to the height of the hierarchy (6.6 KB on Florida), pure Java, no native libraries.
- Everywhere you query: SQL and Cypher, from Java (embedded or client/server), the HTTP API and the drivers.
Apache 2.0, Forever
Customizable Contraction Hierarchies are part of the open source engine starting with ArcadeDB 26.10.2: no enterprise edition, no routing add-on, no per-core license. ArcadeDB is Apache 2.0 forever. Embed it in your product, deploy it anywhere, fork it if you want.
Try It: Tallahassee to Coral Gables on Your Laptop
Everything on this page runs on the Florida road network of the 9th DIMACS Implementation Challenge: 1,070,376 junctions with their coordinates and 2,712,798 road segments with a length (km) and a travel time (minutes). The route-planning use case downloads it and loads it with one request to the GraphBatch endpoint, in about 11 seconds. With Docker:
git clone https://github.com/ArcadeData/arcadedb-usecases.git
cd arcadedb-usecases/route-planning
docker compose up -d # starts ArcadeDB on port 2480
./setup.sh # downloads Florida, loads it, creates the view with CCH (km, minutes)
./queries/queries.sh # every query of this page, through curl
The java folder runs the same queries from a Java client, and embedded/FloridaRoutes.java runs them in an embedded database with no server and no build step: it loads the network with the GraphBatch Java API, compares dijkstra(), astar() and cchShortestPath() on the same route, shows the two costs, and applies the traffic jam.
java -Xmx4g -cp "$ARCADEDB_HOME/lib/*" embedded/FloridaRoutes.java
Through the HTTP API, Tallahassee to Coral Gables takes about 3 seconds with dijkstra(), 6 seconds with astar() and 2 milliseconds with cchShortestPath(). The SQL functions walk the stored records, while the hierarchy reads the in-memory view; the benchmark above compares all three on that same view. The Shortest Path guide covers every option, from the unweighted shortestPath() to A* heuristics, and how to check which engine answered a query.
What is a Customizable Contraction Hierarchy (CCH)?
A CCH is a precomputed structure for point-to-point shortest paths. It ranks the vertices so that the small sets of vertices that split the network sit at the top, adds shortcut edges, and answers a query by climbing from both endpoints to the top. The cost of a query depends on the height of the hierarchy, not on how far apart the two vertices are. It is customizable because the ranking and the shortcuts depend only on the topology: when weights change, only the costs above the changed edges are recomputed.
How much faster is CCH than Dijkstra?
On the DIMACS Florida road network (1.07 million junctions, 2.7 million road segments), CCH answered 12 queries from Tallahassee at increasing distance in 0.010 to 0.041 ms, Dijkstra in 7.8 to 104 ms and A* in 3.1 to 132 ms: 300 to 3,200 times faster than either. Tallahassee to Coral Gables took 0.039 ms with CCH, 99 ms with Dijkstra and 121 ms with A*. Dijkstra's time grows with the length of the route, CCH's does not. Each CCH query used 6 to 43 KB of memory, Dijkstra 11 to 44 MB, A* 9 to 52 MB.
Can the routes follow live traffic and road closures?
Yes. A weight is an ordinary edge property: an UPDATE changes it, and the hierarchy re-prices only the arcs above that edge. On the Florida network a single weight change took 0.8 ms from its commit to a hierarchy answering for it, 100 changes about 41 ms, and a closed road about 1 ms. Queries never wait: until the hierarchy has caught up they are answered exactly by bidirectional Dijkstra.
Do I need a separate routing engine next to my database?
Not for routing over your own network. ArcadeDB keeps the network, its weights and the hierarchy in one transactional engine, so there is no export, no preprocessing job and no sync between a database and a routing service. Dedicated engines built on OpenStreetMap remain the right tool for turn-by-turn navigation on public road maps.
When should I use Dijkstra or A* instead of CCH?
For occasional queries, for networks that change shape all the time, and for graphs without small separators such as social networks or graphs with supernodes, where a hierarchy would be many times larger than the graph. ArcadeDB detects those graphs, marks the hierarchy UNSUITABLE and keeps answering with Dijkstra. Use Bellman-Ford when weights can be negative.
Can one network have several costs, such as distance and travel time?
Yes. A Graph Analytical View keeps one hierarchy per weight property, for example CCH (km, minutes), and keeps all of them up to date together. Each query names the weight it minimizes.
Which query languages can compute shortest paths in ArcadeDB?
SQL, with dijkstra(), astar(), cchShortestPath(), bellmanFord() and shortestPath(), and Cypher, with algo.dijkstra, algo.astar, algo.cch.shortestPath, algo.kShortestPaths and the shortestPath() pattern. Both are available from Java, the HTTP API and the drivers.
Is route planning on ArcadeDB free to use?
Yes. ArcadeDB is Apache 2.0 licensed and free in production, including Customizable Contraction Hierarchies, which are part of the engine starting with ArcadeDB 26.10.2, written in Java with no native dependencies.
Ready to Route on Your Own Network?
Load your network, add one view, and get exact shortest paths in microseconds that follow every change you commit. No routing service to deploy, no pipeline to maintain.