How much space do shortcut edges take compared to the original graph?
A real road network with 65 million nodes and 70 million edges grows to roughly 1 billion edges when all shortcuts are precomputed—about 14× the original size. This fits in memory on a server and is queried in milliseconds; the trade-off favours query speed.
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 & architecture questions
- What does CodeDeploy RESTART actually deploy?
- Does CodeDeploy RESTART work with ECS or Lambda?
- Does RESTART remove an application from load-balancer traffic while it restarts?
- Does Elastic Beanstalk's Active Directory join require a domain password?
- Can an Elastic Beanstalk environment be healthy if the domain join fails?
- Will enabling Active Directory replace running instances?
- What is different about AWS Lambda Web Functions?
- Does Lambda Web Functions automatically cost less than ordinary Lambda?
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 & Architecture beat.