2012/04/06 by Robert Geisberger, Peter Sanders, Dominik Schultes +1 · 4 citations
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Visualization and Analytics
paper · doi:10.1287/trsc.1110.0401
openalex publication_date 2012/04/06 · crossref created 2012/04/06 · crossref issued 2012/08/01 · crossref published 2012/08/01 · crossref published-print 2012/08/01 · crossref deposited 2023/04/02 · openalex created_date 2025/10/10 · crossref indexed 2026/08/03 · openalex updated_date 2026/08/03
Contraction hierarchies are a simple approach for fast routing in road networks. Our algorithm calculates exact shortest paths and handles road networks of whole continents. During a preprocessing step, we exploit the inherent hierarchical structure of road networks by adding shortcut edges. A subsequent modified bidirectional Dijkstra algorithm can then find a shortest path in a fraction of a millisecond, visiting only a few hundred nodes. This small search space makes it suitable to implement it on a mobile device. We present a mobile implementation that also handles changes in the road network, like traffic jams, and that allows instantaneous routing without noticeable delay for the user. Also, an algorithm to calculate large distance tables is currently the fastest if based on contraction hierarchies.