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: https://youtu.be/A60q6dcoCjw?si=5LHOmZ8ZKvR_kLcx If you'd like more information on Minecraft's A*, check out RedLogic's video: https://youtu.be/Zg0Cxn8AVZA?si=DyECX4wmeuSb4c1n ▀▀▀ References: https://ve42.co/DijkstraRefs ▀▀▀ Special thanks to our Patreon supporters: Adam Foreman, Albert Wenger, Alex Porter, Alexander Tamas, André Powell, Anton Ragin, Balkrishna Heroor, Bertrand Serlet, Blake Byers, Bruce, Bryan Ackermann, Chris Brewer, Data Don, Dave Kircher, David Johnston, David Tseng, EJ Alexandra, Evgeny Skvortsov, Garrett Mueller, Gnare, gpoly, Hayden Christensen, Hong Thai Le, Ibby Hadeed, Jeromy Johnson, Jesse Brandsoy, Juan Benet, Kelcey Steele, KeyWestr, Kyi, Lee Redden, Marinus Kuivenhoven, Mark Heising, Martin Paull, Meekay, meg noah, Michael Krugman, Moebiusol - Cristian, Orlando Bassotto, Parsee Health, Paul Peijzel, Richard Sundvall, Robson, Sam Lutfi, Shalva Bukia, Sinan Taifour, Tj Steyn, Ubiquity Ventures, Vahe Andonians, wolfee ▀▀▀ Writers: Sulli Yost Producer & Director: Sulli Yost Presenter: Henry van Dyck & Derek Muller Editor: Jonny Lennard and Trenton Oliver Additional Editor: James Stuart Camera Operators: Sulli Yost & Henry van Dyck Illustrators: Jakub Misiek & Maria Gusakovich Animators: @twoswap, Andrew Neet, Jonny Lennard, Alex Drakoulis & Fabio Albertelli Researchers: Aakash Singh Bagga & Callum Cuttle Thumbnail Designers: Abdallah Rabah, Ren Hurley, Ben Powell & Daniel Ellacott Production Team: Jess Bishop-Laggett, Glen Griffiths, Matthew Cavanagh & Anna Milkovic Executive Producers: Casper Mebius, Gregor Čavlović & Derek Muller Map data © OpenStreetMap contributors, available under the Open Database License: https://www.openstreetmap.org/copyright Additional video/photos supplied by Getty Images and Pond5 Music from Epidemic Sound
ADVERTISEMENT
My dad explained this to me in the early 2000s.. he gave me all this info about the bridges he passed.. but he'd be into this stuff for sure .. he just made a packet and gave it to me about how to do it in real life . Miss my old man .
This is so cool to learn! I didn’t realize Dijkstra’s algo was used to map street routes. I learned about Dijkstra’s when I learned about OSPF routing. The network implementation literally works the same way on how these maps (in general) works! The world around me is wonderful
When I was at Google, I created a bus route tracking algorithm that ran over 10,000 times faster than the Tripfinder algorithm that Maps uses. We had fewer than 100 start nodes and end nodes, so we just put it all in a Spanner table with two columns as the search key. 😄
I'm so happy for the 2swap collaboration
It's crazy how Derek made better videos than an entire production company. Hard to stay awake through the most recent videos.
I found this family of algorithms back in 2009 and used it in order to help design a warehouse picking system. Very useful.
Wow I didn't even need subtitles for what Dijkstra said! Amazing!
Danke fürs erklären, Ben👍🏻
I would love a Part 2 to explain how they convert roads into a meaningful data structure. How do towns provide the needed data on road closures? How does the algorithm know which roads are one-way? How do you know which roads have center barriers that prevent left turns? Etc.
I enjoyed graph theory a lot during my studies - glad to see it back!
5:42 A triangle can never have 2 sides of 2 and 1 side of 5 because 2+2 is smaller than 5...
4:41 i independently invented this algorithm in high school after learning about recursion, though mine was depth-first, so it would probably be very inefficient with complex route networks
I am actually so happy that Rotterdam en Groningen where correctly pronounced. It is not often that I here that in a English video. 2:11
I found really interesting videos like this one, that explains the insane ammount of thought put into so mundane and daily things, that we don´t bother to get a clue about how they work.
Dijkstra's theorem is so simple yet so elegant.
4:16 voice actor in this part feels like an ai copy of Derek
I love your videos so much. Over the years, these are the pieces of science I remember the most. The way you teach by telling stories is memorable for me. I also love the focus on the human side behind the science, it really grounds the whole story. Thank you for everything you do!
A really thoughtful presentation on something I hadn't thought about , maybe in forever. I think my chief take away is the notion of weighting the routes and using them to calculate the route.
the collab we never knew we needed
28:57 here is a better translation: If it doesn’t work, you simply did it wrong