An augmented graph, also called an overlay graph, is the original weighted graph with shortcut edges added. It is built during contraction hierarchy (CH) preprocessing so a shortest-path query can skip less important nodes without losing the distances those nodes helped establish. The graph retains the original vertices and edges; contracting a node does not delete it from the finished augmented graph. section 4.3.4
A shortcut through a contracted node
Suppose the shortest route from u to w passes through v and costs 5. When v is contracted, add an edge from u to w with cost 5 if it is needed to preserve that distance. If another path already reaches w at a lower cost, that path is a witness that the shortcut is unnecessary. The added edge represents travel through v; it is not a new road. section 4.3.4
To build and use the graph:
- Choose an importance order and contract nodes from least to most important. For a road network, road type can inform importance; speed, tolls, and turns are other possible heuristics. section 4.3.4
- For paths through each node being contracted, add the shortcuts needed to preserve shortest distances. Keep the original edges as well as the new ones. section 4.3.4
- Run a shortest-path query on the preprocessed graph, considering increasingly important edges. A bidirectional Dijkstra search can then bypass many less important nodes. section 4.3.4 section 4.5
- Unpack shortcuts when the actual route is needed: a result using shortcut (8,5), for example, expands it into (8,3) and (3,5). section 4.3.4
The trade-off is preprocessing time and added edges in exchange for faster queries. A NetworkX implementation with a predetermined node order illustrates the build phase by comparing weighted shortest-path lengths before and after removing a node. Try changing the node order and inspecting which shortcuts become necessary; the augmented graph is useful beyond road networks, but the chosen importance heuristic affects how effectively queries can skip nodes. 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 need not always create a shortcut: an alternative shorter path already serves the connection. section 4.3.4
