Why contract low-degree nodes first instead of high-degree ones?
Contracting a node creates shortcut edges between all pairs of its neighbours. A node with 100 neighbours creates ~5,000 shortcuts; a degree-1 node creates none. Contracting low-degree nodes first adds shortcuts gradually, reducing the overhead when high-degree junctions are processed late.
Answered in
Why Google Maps Computes Shortcuts OfflineContraction Hierarchies precomputes shortcut edges offline so routing queries skip neighbourhood streets and touch only 2,000 nodes in under 10 milliseconds.
Read the full analysisOther questions this article answers
More system design questions
- Why doesn't Google just run Dijkstra faster?
- What is a shortcut edge and when is it precomputed?
- How much space do shortcut edges take compared to the original graph?
- Can Contraction Hierarchies handle dynamic graphs like traffic or road closure?
- What is a CRDT and why does it matter for real-time collaboration?
- How do CRDTs handle concurrent edits without a central server referee?
- Why did Figma move from operational transforms to CRDTs?
- What's the memory and bandwidth cost of running replicas locally?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design beat.