At the core of Google Maps: Dijkstra's Algorithm

Google Maps and the other satellite routing apps are rooted in Network Science. They divide the problem of serving you the best route into smaller, simpler problems. These apps use large datasets to represent roads and streets as a graph, with intersections as nodes and road segments as edges. Then, they rely on an algorithm more than half a century old, that allows us to quickly calculate the shortest paths on graphs. Dijkstra's algorithm is at the very centre of how Google Maps works and at the very centre of this video. While Dijkstra's algorithm provides the shortest path on the graph, additional steps are necessary to determine the fastest directions. This is where big data comes into play. By leveraging real-time information on traffic congestion and incidents from a crowd-sourced network, the shortest path is transformed into the quickest one.
More about me: 👉 linktr.ee/erik_hormann
Let's connect: 👉 / erik_hormann
Please let me know what you think of my videos in the #commentsection 👇 and #like 👍 #subscribe ▶️ and ring the #bell 🔔 to stay up-to-date with all the videos I release! Feel free to ask me any #question ⁉️
00:00 Intro
00:35 Road Modelling
03:00 Dijkstra's Algorithm
11:00 Traffic Modelling
12:47 Outro

[@srinathtankasala]

I don't think Google Maps uses Djikstra's algorithm or models entire roads as a single edge. If you did that, then you can't get point to point navigation like how it does. Google Maps can calculate routes between cities 1000 miles apart in seconds and even re-routes on the fly when you make a mistake. They must have a really fine grained and high resolution map/graph with additional nodes to account for road lanes, left/right turn only lanes and other such features. My guess is they are using A-star with a learnt heuristic function.

[@StronglyConnect]

Thanks for watching! I agree about the incredible granularity of the data they must posses. After all, we're talking about a project that has seen two decades of constant work and improvements from Google, so it's not surprising. As far as I know, A-star is an informed version of Dijkstra, and in the exploration phase preference is given to nodes that are in the general direction of your target node. This requires either geolocation or prior knowledge of the graph, which could be obtained by a pre-run of Dijkstra. It's an interesting point though, thanks!

[@mustafajawed918]

A great way of explaining with real world examples! Keep up the good content 👏

[@StronglyConnect]

Thanks, will do!

[@hajorda6540]

Last day i took this on algorithm 2 class and here we go. thanks for video.

[@StronglyConnect]

Just in time then... I bet they didn't talk about the shopping story, though! (at least, my professor never did)

[@izaakwhite1596]

clutch for my data structures final

[@StronglyConnect]

Hope it helped!

[@yannick4252]

I enjoyed it 😊

[@StronglyConnect]

Yay! Thank you!

[@leonardorodovero4989]

Can you make a similar video using the same algorithm but for path tracing in images?

[@StronglyConnect]

I’m not familiar with that application of this algorithm but will certainly have a look a it! Thanks for the suggestion, hope you liked the video

[@shashank9250]

interestinh

[@StronglyConnect]

Thanks, glad you liked it!