Introduction
The Shortest Path Problem
Shortest-path queries on road networks are an example of how a classical algorithm with good theoretical bounds may not always achieve practical efficiency. For example, a road network is just a very large directed graph, where edges are roads and intersections are vertices. Dijkstra’s algorithm, we know, offers an efficient method to finding the shortest path between two points in a graph.
But when the graph has millions of nodes and edges, as road networks do, the disparity between good theoretical performance and good real-life performance becomes apparent. Given the growing prevalence of real-time navigation and location-based services, we need to be able to query shortest-paths in large road networks in a small fraction of the time that traditional algorithms use (think microseconds as opposed to seconds).
Route-planning algorithms, then, are an extension of Dijkstra’s algorithm, where the specific problem is to query the shortest path from source to target in a road network as quickly as possible.
Recent work on route-planning algorithms has been extensive. In general, both technical and graph-theoretical heuristics can be used to massively reduce the search space of a graph when running Dijkstra’s algorithm. Contraction Hierarchies provide a useful approach in offering large query speedups with only a modest tradeoff in preprocessing time.
The Roadmap
This site begins by introducing some of the basics on graphs, road networks, Dijkstra’s classic shortest-path algorithm. We then build some motivation for how we could augment a road network graph with useful information, and in turn achieve faster queries.
Then we introduce the core components of contraction hierarchies in detail, and we see how its unique approach is correct and offers good results. The sections that follow are intended to be read in order and should provide a reader with a strong grasp of the fundamental aspects of contraction hierarchies.
Continue on below!