Google Maps Won't Find the Fastest Route

Описание: In this video I try to explain why Google Maps doesn't actually search the road network when you tap go. The fastest route exists, but searching for it across a hundred million roads would take minutes, so Google does the search ahead of time, on its own servers, and ranks every intersection by importance into a giant pyramid called a contraction hierarchy. When your query lands, the app runs two tiny searches that climb the pyramid from both ends and meet in the middle in under a millisecond. I walk through why Dijkstra and A* aren't fast enough, how shortcuts collapse twenty intersections into one pretend road, and how traffic gets stitched in without rebuilding the whole graph.

Timestamps:

0:00 Intro
0:16 How people think Google Maps works
0:57 Why classic algorithms are too slow
1:57 Google's trick: pre-compute everything
2:48 Shortcuts and the pyramid
4:06 Building the pyramid
4:23 How your search actually runs
5:14 Handling live traffic
5:54 Recap
6:29 Subscribe

I put a lot of time into these videos. If you'd like to support the channel, you can buy me a coffee here: https://buymeacoffee.com/decomplex. Honestly though, the biggest support is just hitting subscribe and leaving feedback in the comments. That helps way more than anything else. Thank you and see you in the next one!