Contraction Hierarchies

In applied mathematics, the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contracted" versions of the connection graph. It can be regarded as a special case of "highway-node routing".

Contraction hierarchies can be used to generate shortest-path routes much more efficiently than Dijkstra's algorithm or previous highway-node routing approaches, and is used in many advanced routing techniques. It is publicly available in open source software to calculate routes from one place to another.

In general, scalable map routing algorithms have two distinct phases: preprocessing of the original graph (which may take more than an hour to finish) and queries (less than a second). Contraction hierarchy (CH) is an extreme case of "hierarchy" approach, which generates a multi-layered node hierarchy in the preprocessing stage. In a CH, every node in the graph is represented as its own level of hierarchy. This can be achieved in many ways; one simple way is simply to label each node in order of some enumeration from 1 to N, where N is the number of nodes in the graph. More sophisticated approaches might consider the type of road (highway vs minor road, etc.).

CHs have been extended to a three phase setup called CCH that supports flexible edge weights. In this setup there is a slow (hours) preprocessing phase, a reasonably fast (about a second) customization phase and a very fast (milliseconds) query phase. In the preprocessing phase only the graph but not the edge weights are revealed to the algorithm. In the customization phase the weights are revealed and in the query phase shortest paths are computed. Changing the weights of the graph requires only rerunning the customization phase but not the preprocessing phase. It is therefore possible to exchange the edge weights within seconds. This setup enables live-traffic updates and routes can easily be adjusted to user specific preferences. An open-source CCH implementation is available.

...
Wikipedia