A shortcut edge is an added edge that stands in for a path through a contracted node. In a road network, it lets a shortest-path query bypass a less important intersection without losing the cost of traveling through it. Shortcuts are created during contraction hierarchy preprocessing, before routes are queried. section 4.3.4
Contracting one node
Suppose directed edges u→v and v→w form a shortest path. When v is contracted, add u→w with the combined cost of that path. If another path from u to w is shorter, that path is a witness: no shortcut is needed for this pair. The test matters because adding every possible shortcut would enlarge the graph unnecessarily. section 4.3.4
A practical contraction hierarchy uses shortcuts in two phases:
- Preprocess: rank nodes by importance, contract them from least to most important, and add shortcuts where contraction would otherwise disrupt shortest paths. Road type is one possible basis for importance. section 4.3.4
- Query: run bidirectional Dijkstra’s search on the augmented graph, following edges toward increasingly important nodes rather than exploring every less important node. section 4.3.4
- Recover the route: replace each shortcut in the returned path with the original path it represents. A worked route expands shortcut (8,5) into (8,3) and (3,5). 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 the key decision before adding a shortcut: an alternative shorter route can make the proposed edge unnecessary. section 4.3.4
The trade-off is preparation time for faster queries. An illustrative Python implementation uses NetworkX shortest-path lengths to examine the effects of removing nodes; its node order is predetermined. On a larger graph, both the ordering and the shortcuts it produces matter: contracting a hub can create many added edges. Try changing the contraction order on a small weighted graph, then compare the shortcuts added and verify that unpacked routes still follow original edges. section 4.3.4 section 4.5
