Contraction hierarchies
In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph.
Intersections are represented by vertices, the road sections connecting them by edges.
The edge weights represent the time it takes to drive along this segment of the road.
The shortest path in a graph can be computed using Dijkstra's algorithm but, given that road networks consist of tens of millions of vertices, this is impractical.
[1] Contraction hierarchies is a speed-up method optimized to exploit properties of graphs representing road networks.
[2] The speed-up is achieved by creating shortcuts in a preprocessing phase which are then used during a shortest-path query to skip over "unimportant" vertices.
Contraction hierarchies are not only applied to speed-up algorithms in car-navigation systems but also in web-based route planners, traffic simulation, and logistics optimization.
As road networks change rather infrequently, more time (seconds to hours) can be used to once precompute some calculations before queries are to be answered.
To calculate the distance between these two cities, the algorithm has to traverse all the edges along the way, adding up their length.
Precomputing this distance once and storing it in an additional edge created between the two large cities will save calculations each time this highway has to be evaluated in a query.
The contraction hierarchies algorithm has no knowledge about road types but is able to determine which shortcuts have to be created using the graph alone as input.
As the number of shortcuts is the primary factor that determines preprocessing and query runtime, we want to keep it as small as possible.
This can, for example, be done by maintaining a counter for each node that is incremented each time a neighboring vertex is contracted.
[11] Top-down heuristics, on the other hand, yield better results but need more preprocessing time.
Nested dissections can be efficiently calculated on road networks because of their small separators.
[2] This, in combination with how shortcuts are created, means that both forward and backward search only need to relax edges leading to more important nodes (upwards) in the hierarchy which keeps the search space small.
To obtain the list of edges (roads) on the shortest path, the shortcuts taken have to be unpacked.
Storing the middle vertex of each shortcut during contraction enables linear-time recursive unpacking of the shortest route.
In the preprocessing phase, most of the runtime is spent on computing the order in which the nodes are contracted.
Other applications include matching GPS traces to road segments and speeding up traffic simulators which have to consider the likely routes taken by all drivers in a network.
In route prediction one tries to estimate where a vehicle is likely headed by calculating how well its current and past positions agree with a shortest path from its starting point to any possible target.
Typical examples include finding the closest gas station, restaurant or post office using actual travel time instead of geographical distance as metric.
[2][3] Some applications even require one-to-all computations, i.e., finding the distances from a source vertex
As Dijkstra's algorithm visits each edge exactly once and therefore runs in linear time it is theoretically optimal.
[2] CHs can be extended to optimize multiple metrics at the same time; this is called multi-criteria route planning.
[2] A number of bounds have been established on the preprocessing and query performance of contraction hierarchies.
The first analysis of contraction hierarchy performance relies in part on a quantity known as the highway dimension.
While the definition of this quantity is technical, intuitively a graph has a small highway dimension if for every
[18] An alternative analysis was presented in the Customizable Contraction Hierarchy line of work.
The main source is [19] but the consequences for the worst case running times are better detailed in.
