Google Maps HLD: Fastest Route on a Planet-Sized Graph

You tap a pin near a coffee shop across town, hit Directions, and before your thumb is off the glass a blue line has already threaded twelve miles of streets, turned down the one road that dodges the jam on the bypass, and told you it's nineteen minutes away. It feels like the app simply knows the way. It doesn't. In the time it took you to glance up, a machine searched a graph with hundreds of millions of road segments — where the weight on every edge is changing as traffic moves — and pulled out the single fastest path through it. Do that the obvious way and you'd scan half a continent for o…