Chapter 5

Introduction to Contraction Hierarchies

To achieve fast shortest path queries with minimal memory overhead, we make use of Contraction Hierarchies, a hierarchical routing technique proposed by Geisberger et al. [Geisberger2008, pages 319-320]. This method preprocesses the graph by adding shortcut edges and organizing nodes by importance, allowing queries to navigate only through the most relevant parts of the graph.

Algorithm Description

Each node is assigned an importance value. Nodes that appear in more shortest paths are considered more important (e.g., highway entry vs. residential intersection). The key preprocessing step is to contract nodes from least to most important. Contracting a node means removing it from the graph, but before doing so, we insert shortcut edges that preserve shortest path distances for any path that would have passed through the removed node.

Specifically, for every pair of neighbors $u, w$ of a node $v$, if the shortest path from $u$ to $w$ passes through $v$, we add a shortcut edge $(u, w)$ with weight $t(u, v) + t(v, w)$.

Below is an example of contracting a single node (C) and the shortcuts added as a result:

This contraction process is repeated for all nodes in increasing order of importance. In our example, nodes are contracted in alphabetical order: A, B, C, D, E. We invite the curious reader to determine why no shortcut is created at the beginning from C -> B.

After contraction, the graph contains the original edges plus all added shortcuts:

Key Properties of the Contracted Graph

We have:

1. Any shortest path from $s$ to $t$ can be represented as a sequence of edges where node importance first increases to a peak node $v^*$, then decreases—forming a “hill shaped” path in the hierarchy.
2. Edges going from lower to higher importance form the upward graph (a DAG), while edges going from higher to lower importance form the downward graph (also a DAG).

In our running example this looks as follows. Added shortcut edges are emphasized.

Shortest Path Querying

These key properties enable efficient bidirectional search restricted to the two directed acyclic graphs.

To compute the shortest path between nodes $s$ and $t$:

1. Perform a forward Dijkstra search from $s$ using only upward edges.
2. Perform a backward Dijkstra search from $t$ using only downward edges.
3. The searches meet at the highest ranked node along the shortest path.

This bidirectional search over the contracted graph is extremely fast. On the New York City road network, average query time is 0.026ms [FastPaths].

We will not discuss the detailled running time and memory usage for point-to-point routing here, as point-to-point shortest path queries are not our main interest. However, most of the analysis is similar to what we will discuss in the next section for our problem of interest.

Time Complexity

The time complexity depends on multiple factors:

1. The structure of the Graph
2. The order of contraction
3. The implementation of shortestPathViaContractNode

We will discuss how graph structure and contraction order affects the construction time complexity in the next chapter. When it comes to the choice of implementation shortestPathViaContractNode, there is a tradeoff to be made between fewer added shortcuts and faster computation. We could simply check if a direct edge exists between $u \to w$ and only add the shortcut if that direct edge does not already exist (or update the weight if it does).

Alternatively, we could run Dijkstra and determine if a shortest path between $u \to w$ does indeed go through the contracted node. Running Dijkstra is much more expensive than checking for a direct edge, but it may lead to fewer shortcuts being added (which is good for our query time performance). One might also consider a middle ground approximation of some sort.

In the worst case however, where we are constructing a Contraction Hierarchy on a complete graph where every node is most efficiently connected to every other node by a single edge, the construction time complexity is $\mathcal{O}(V^3 \cdot shortestPathViaContractNode)$, where $\mathcal{O}(shortestPathViaContractNode)$ is $\mathcal{O}(1)$ for the simple edge check vs $\mathcal{O}((V + E) \log V)$ for Dijkstra.

Space Complexity

The space complexity also depends strongly on the number of shortcuts added during the contraction process. In the worst case where we end up storing a complete graph with every node connected to every other node, the space complexity is $\mathcal{O}(V^2)$.

Next Steps

Two questions remain:

1. How do we compute good importance values for nodes efficiently?
2. How can we adapt Contraction Hierarchies to our goal of efficiently filtering listings by travel time?