Preprocessing
Order nodes by 'importance' (heuristic). Contract nodes bottom-up: remove and add shortcuts to preserve distances.
Advertisement
Query
Bidirectional Dijkstra, only ascending edges (u→v where importance[v] > importance[u]). Meet in middle.
Advertisement
Speedup
Query O(1000s of edges) on continental road network with 100M nodes. Sub-millisecond routes.
Preprocessing cost
Hours for continent-scale graphs. One-time cost, amortized over billions of queries.