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.
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!
Great explanation, Erik, well done. I have a question about the ETA calculated by Google Maps. Is it based on my Google profile and tracked driving data, or is it a generic ETA calculated for anyone? It's fascinating to see the ETAs' accuracy, whether I'm driving 5 miles, 50 miles, or more.
As far as I know, it’s standard for everyone but based on every user who is using the service, i.e. if many users slow down on a stretch of road, your prediction gets upped if you need to pass over the same road. I don’t work for Google though so really only THEY know how it works! Also thanks for the kind words!
A great way of explaining with real world examples! Keep up the good content 👏
Thanks, will do!
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.
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!
Great explanation, Erik, well done.
I have a question about the ETA calculated by Google Maps. Is it based on my Google profile and tracked driving data, or is it a generic ETA calculated for anyone?
It's fascinating to see the ETAs' accuracy, whether I'm driving 5 miles, 50 miles, or more.
As far as I know, it’s standard for everyone but based on every user who is using the service, i.e. if many users slow down on a stretch of road, your prediction gets upped if you need to pass over the same road. I don’t work for Google though so really only THEY know how it works! Also thanks for the kind words!
Last day i took this on algorithm 2 class and here we go. thanks for video.
Just in time then... I bet they didn't talk about the shopping story, though! (at least, my professor never did)
Can you make a similar video using the same algorithm but for path tracing in images?
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
clutch for my data structures final
Hope it helped!
I enjoyed it 😊
Yay! Thank you!
interestinh
Thanks, glad you liked it!