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
I'm so glad the mighty 2swap is generous enough to share the spotlight with underrated obscure indie creators such as Veritasium
Every first year CS student is giggling with joy at this video
Nice touch using the Dijkstra font in the video! Met Dijkstra a couple of times while at university. An amazing man.
All roads lead to Dijkstra's Algorithm
VERITASIUM AND 2SWAP COLLAB HELL YEAH
As a Dutchman, I'm so happy Dijkstra got pronounced Dijkstra, and not butchered into Diekstra or something.
Dutch Casper isn't real, it can't hurt you
I love that the map at 6:47 shows the Netherlands as it existed in 1956, i.e. before Flevoland was created. Nice detail! I also find it very interesting that Casper (who is Dutch and has a slight Dutch accent) is consciously adopting a thicker, more common Dutch accent while voicing Dijkstra. He's making himself sound more Dutch than he usually does.
I love when huge youtubers like 2swap Collab with smaller creators, it's really inspiring
I absolutely **LOVE** that you guys used Dijkstra's font for subtitles of what Dijkstra said! Love that subtle detail! Dijkstra's handwriting was amazing!
28:08 "Simplicity is pre-requisite for reliability"
Nodes in a funnel Cascade into the target Like a lily's dew
Veritasium and 2swap. Wow!
Absolute heavenly collab
Click this link /?promo=VERITASIUM and use our code VERITASIUM to get 25% off your first payment for boot.dev.
16:00 I'm French, I laughed when he called that landing strip a narrow road, you could drive three cars down that and still have room to spare
that ending comment at 29:11 hit me the hardest, im always trying to make things easier and more efficient for others to use, whether its software to complete a task or a simple mechanical/engineering/MacGyver fix, making your daily tasks easier is what i enjoy doing.
Veritasium is just collaborating with any edu youtube channel I'm subbed to 😂😂
0:14 yeah such a small number less than the possible knots in my earphone in my pocket
Never thought I’d see a RainWorld reference in Veritasium, of all places.