Preprocessing is work done on data before a query so that later queries can run faster. In shortest-path routing, contraction hierarchies preprocess a graph by ordering nodes by importance and adding shortcut edges. The result is an augmented graph and a node order for the query phase. The upfront work takes time, but subsequent searches can examine far fewer nodes. section 4.3.4
For a weighted directed graph, the preprocessing workflow is:
- Rank nodes by importance, then contract them from least important to most important. section 4.3.4
- When contracting a node, add shortcuts where needed to preserve shortest paths. If another shorter path already exists—a witness path—the shortcut is unnecessary. section 4.3.4
- Keep the augmented graph and node order. At query time, search toward increasingly important nodes rather than revisiting the entire original graph. section 4.3.4
Why pay the upfront cost?
For one 80-mile source-to-destination query, bidirectional Dijkstra’s search explores about 220,000 nodes, unidirectional A* about 50,000, and bidirectional A* about 25,000. A contraction-hierarchy query explores about 600. These figures illustrate the potential payoff for fast queries, not the cost of building the hierarchy. section 4.3.4
Figure 4.24 Witness path—there is another path from P to w that is shorter, so no shortcut is needed when contracting v.
The witness-path diagram shows why contracting a node does not always require a new shortcut: another path can already be shorter. section 4.3.4
Listing 4.6 Contraction hierarchy with predetermined node order
import networkx as nx
shortcuts = {}
shortest_paths = dict(nx.all_pairs_dijkstra_path_length(G,
weight="weight"))
current_G = G.copy() #1
for node in G.nodes:
current_G.remove_node(node) #2
current_shortest_paths = dict(
nx.all_pairs_dijkstra_path_length(current_G, weight="weight")
) #3
for u in current_shortest_paths:
if u == node:
continue
SP_contracted = current_shortest_paths[u]
SP_original = shortest_paths[u]
for v in SP_contracted:
if u == v or node == v:
continue
if (
SP_contracted[v] != SP_original[v]
and G.has_edge(node, u)
and G.has_edge(node, v)
):
G.add_edge(u, v, weight=SP_original[v],contracted=True) #4
shortcuts[(u,v)] = node #4
#1 Copy the main graph so that the nodes are only removed from the copy, not the main graph.
#2 Contract the node by removing it from the copied graph.
#3 Recalculate the shortest path matrix, now with the node contracted.
#4 Add a shortcut edge to replace the changed shortest path, and keep track of it so we can uncontract it when querying later.
The NetworkX listing provides a Python example of contraction-hierarchy preprocessing with a predetermined node order. section 4.3.4
After preprocessing, bidirectional Dijkstra’s search can use the augmented graph to answer a source-to-target query. A returned route may contain shortcuts; unpacking them recovers the route through the original nodes. The trade-off is therefore deliberate: spend time preparing the graph to make later searches fast. section 4.3.4 section 4.5
