Conclusion
Summary and Advanced Results
We’ve now explored the fundamentals of the contraction hierarchies route-planning algorithm!
To summarize we’ve:
Become familiar with the nature of road networks and the algorithmic challenges involved in shortest-path queries.
Seen how road networks have a hierarchical nature that can be exploited during searches.
Learned how a bidirectional Dijkstra search gives us some initial speedup.
Walked through the core components of CH, including main the contraction process.
Proved the correctness of the CH modified bidirectional query for any node ordering.
Discussed the advantages and heuristics used to compute a good node ordering.
Further Discussion
In general, it’s worth mentioning that implementations of the contraction hierarchies algorithm achieve maximum speedups with some of the finely tuned heuristics we mentioned for node ordering and also querying.
However, providing theoretical bounds for these speedups can still be challenging, especially if we consider other graphs that do not necessarily represent road networks. The work in [1] gives a good initial coverage of a few assumptions and bounds, but a full discussion is beyond the scope of this site.
Static vs. Dynamic
Additionally, note that this discussion of contraction hierarchies mostly assumed that edge weights were fixed. More realistically, we would want to consider scenarios where edge weights could be changed quickly so that queries return updated shortest paths in the case of traffic or road closures. [4] and [6] give some discussion on modified versions of contraction hierarchies to better enable dynamic edge costs.
Contraction hierarchies can also be used as a method for categorizing nodes in other shortest-path algorithms. These hybrid algorithms might not rely on the bidirectional CH query, but instead use the notion of contraction to categorize nodes during various preprocessing routines. See [10] and [2] for more coverage of various hybrid techniques.
Please see the full references page for more information and reading.