Core Components of CH
Conceiving Contraction Hierarchies
So given our (provably correct) bidirectional search variant, and the hierarchical heuristic we previously established, we now have a few useful components that can form the basis of a much faster algorithm.
Combining the two components we could:
(1) Preprocess: categorize nodes and edges basd on some notion of importance.
(2) Query: run a bidirectional search that only considers increasingly important edges.
In fact, [12] used this template when designing the Highway Node Routing (HNR) algorithm, which implements the idea of Highway Hierarchies from [10] to create a node ordering.
This relies on a process of edge reduction, where edges that are unlikely to appear in the middle of a shortest path (i.e. non highways) are removed from the graph. What results is a set of hierarchical levels which then guide the bidirectional search. But using edge reduction as a method for creating a node ordering is costly (see [8]).
Instead the Contraction Hierarchies algorithm uses a process of node contraction to create a hierarchy in which every node belongs to a unique level (in other words, an ordering of nodes based on importance).
During the contraction process, a set of shortcut edges is added to the graph that preserves shortest paths. The bidirectional search then only considers the subset of edges that lead from less important to more important nodes, and these edges might include the shortcuts we added. The result is faster querying with only a modest increasing in preprocessing compared to Highway Node Routing.
So we can present a full overview of the CH algorithm as a reference, and the sections that follow give an analysis of each core component in greater detail.
The High-Level CH Algorithm:
Preprocess:
- Order nodes based on some computed level of importance.
- Contract each node in order of least important to most important.
Query:
- Run a bidirectional Dijkstra search, but only consider edges leading to nodes with a higher importance.
For now, we look more in depth at the concept of node contraction.