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

"Design Google Maps" and the centre of gravity is one query: the fastest route from here to there, returned in milliseconds, on a graph with hundreds of millions of road segments, with the weights changing as traffic moves. The road network is a weighted graph and the route is a shortest path — but the Dijkstra you already know floods outward in every direction and would visit half a continent before it reached your destination. Maps needs to be smarter about where it looks and to precompute so a single request never scans the whole planet. Two ideas carry the design: a heuristic that aims the…