Contraction hierarchies

In applied mathematics, the method of contraction hierarchies is a technique to simplify 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 open source software.

The algorithm

Note: this description is based on tutorial material by Ivan Škugor.

In general, scalable map routing algorithms have two distinct phases: preprocessing of the original graph (usually it takes more than a hour to finish) and queries (less than a second). Contraction hierarchy is extreme case of "hierarchy" approach, which generates a node hierarchy in the preprocessing stage. In CH every node in the graph is represented as its own level of hierarchy. This can be achieved in many ways, but one way is obvious and simple. If |N| is number of nodes in the graph, every node is enumerated from 1 to |N|. That way in hierarchy every node is represented as distinct level.

Levels/order of nodes in CH can be arbitrary. The main point is that shorcuts are introduced when necessary. To understand when a shortcut is necessary, one has to understand the searching algorithm. The searching algorithm (bidirectional Dijkstra's algorithm) only relaxes edges that are connected to the nodes that are higher in CH than current node in one direction, and vice versa. That way, the algorithm wouldn't find shortest paths and because of that we need to introduce new edges to the graph that represents existing shortest paths that algorithm doesn't take into consideration. Not all shortest paths needs to be restored as new shortcut edges, it's enough to take in consideration adjacent nodes of some node that are higher in CH (sub-path of some shortest path is shortest path himself).

Algorithmically:

• Add order/levels to the graph nodes
• For each node, respecting order, get its adjacent nodes of higher order and find if shortest path between each pair of them goes through current node and if it is, add shortcut edge

Preprocessing

Let's say that we take in cosideration just 2 adjacent nodes (from, in general, "n" of them):

From this picture, if shortest path from v to w goes through node u that is lower in CH, new egde has to be added the CH graph so that shortest paths that searching algorithm takes in consideration are preserved.

Weight of new egde is equal to path distance from v to w.

When preprocessing of the original graph is is done, we need to build CH graph which consists of node order and original graph with shortcut edges introduced in preprocessing stage.

Querying

For the searching algorithm, bidirectional Dijkstra's algorithm is used. It is classical Dijkstra's algorithm with some modifications. The algorithm searches from starting node in one direction and from ending node in other direction (this is classical bidirectional Dijkstra's algorithm), but it relaxes edges that are directed toward higher hierarchy nodes in one direction (essentially it expands towards higher hierarchy nodes) and edges that are directed toward lower hierarchy nodes in other direction. That way, the searching algorithm wouldn't find all shortest paths, because it doesn't take in consideration shortest paths that aren't directed in a way the algorithm searches. To restore shortest paths that aren't taken into consideration, a new edge is added to the graph. That edges are called shortcut edges and they represents existing shortest paths between two nodes in the graph.

On CH graph we can make queries to find shortest paths with modified bidirectional Dijkstra's algorithm - algorthm performs forward search from starting node s expanding to the nodes that have higher order and backward search from target node t to the nodes that have lower order. If the shortest path exists, those two searches will meet at some node v. A shortest path from s to t consists from paths from s to v and from v to t.

The shortest paths found by this algorithm have particular form:

$<s=u_{0},u_{1},...,u_{p}=v,...,u_{q}=t>,p,q\in N$

$ui<u_{i+1}zai\in N,i<p$

$uj>u_{j+1}zaj\in N,p\leq j<q$

A path found by a query is the shortest path because of preprocessing stage. In preprocessing stage we transformed graph introducing shortcut edges,which represents the shortest paths that algorithm does not take into consideration.

In order to demonstrate that this algorithm retrieves shortest paths, consider it by contradiction: let's assume (for forward search, identical thing stands for backward search) that there exists a path that is shorter than the one we found with this algorithm:

Let's say that at some point there exists a subpath that is shorter than path. Because algorithm expands towards nodes that have higher order, order of $u_{k}$ node must be lower than order of $u_{k-1}$ and $u_{k+1}$ nodes. Because of that fact, in preprocessing stage that path would be represented as shortcut edge with equal length, and therefore no such path that is shorter than the one algorithm found can exists.

Further reading

• Contraction hierarchies described on qscribble blog