Contraction Hierarchies Algorithm

Contraction hierarchies is a speed-up technique for computing shortest paths in large graphs, developed especially for road networks used by car navigation systems, web based route planners, and logistics software where the same graph is queried for shortest routes over and over again. In a one-time preprocessing phase, the algorithm repeatedly removes, or contracts, vertices from the graph in an order chosen by an importance heuristic, and whenever removing a vertex would break the shortest path between two of its remaining neighbors, it adds a shortcut edge between them that preserves the original shortest distance. A later query for the shortest path between two points then runs a bidirectional search that starts from both endpoints at once and only follows edges leading toward more important vertices, which keeps the search confined to a small fraction of the full graph and answers queries far faster than running an unmodified shortest path algorithm on the whole network. Robert Geisberger, Peter Sanders, Dominik Schultes and Daniel Delling introduced the technique in 2008.