Table of Contents

Introduction

• The Shortest Path Problem
• Road Network Basics
• Dijkstra’s Algorithm
• Speedup Approaches

CH Warmups

• Hierarchies of Road Networks
• Bidirectional Search

Core Components of CH

• Conceiving Contraction Hierarchies
• Node Contraction
• Adding Shortcuts
• The CH Query
• Query Correctness
• Choosing a Node Order

Conclusion

• Summary and Advanced Results