https://invidious.nerdvpn.de/watch?v=kS-CGkiPetQ https://www.youtube.com/watch?v=kS-CGkiPetQ
The math behind Google Maps. Sponsored by boot.dev - Click this link https://boot.dev/?promo=VERITASIUM and use our code VERITASIUM to get 25% off your first payment for boot.dev.
If you’re looking for a molecular modelling kit, try Snatoms, a kit I invented where the atoms snap together magnetically - https://ve42.co/SnatomsV
Sign up for the Veritasium newsletter for weekly science updates - https://ve42.co/Newsletter
For those curious about the path-count estimate: we estimated the non-backtracking paths NYC→SF, using a sparse spatial network model with mean degree ≈ 2.5 and characteristic length ≈ √N.
0:00 What is a ‘shortest path algorithm’? 3:30 Dijkstra’s 20 Minute Algorithm 6:30 The First Route Planner 10:31 A* Search Algorithm 12:40 Shortest Doesn’t Mean Fastest 15:08 Road Network Hierarchy 18:29 Mapping North America - Nested Dissection 25:17 How do map apps work? 28:04 Simplicity is prerequisite for reliability
Check out @twoswap's channel for some fantastic videos!
A big thank you to Ben Strasser and Julian Dibbelt who were incredibly gracious with their time and feedback.
Thank you to all the experts we interviewed for this video: Aaron Bernstein, Tim Roughgarden, Tomas Rokicki, Jon Kleinberg, Virginia Vassilevska Williams, Peter Sanders, and the team behind the SSSP Barrier Paper: Xinkai Shu, Ran Duan, Xiao Mao, Longhui Yin, Jiayi Mao
For more information on how you choose A's heuristic, check out Polylog's video: • The hidden beauty of the A algorithm
If you'd like more information on Minecraft's A*, check out RedLogic's video: • Minecraft’s Smartest System Is Almost Comp...
References: https://ve42.co/DijkstraRefs