I'm a trucker with many loads from LA to NYC. Simple... take the 40 to the 81 in TN exit 421, then north to the 80 and into NYC. Why? Weather and terrain.
3:48 This is a surprisingly tough thing for students to get past, because in the graph you've drawn it's obvious by look that you have to go through H or G so you should head to those points immediately, but as you've correctly said the algorithm doesn't know that (and also finding such points by an algorithm feels like it would take |V|² time), and students often have trouble with the incomplete information part of programming. What I like to do when showing the algorithm in practice is to completely hide the rest of the graph in a kind of "fog of war" : It's not just that you don't know where X is, you don't even know any of the points that aren't X or A until you've been near them. It's easier to do in manim, but you can do that with a piece of paper on a whiteboard. Maybe the shortest path goes through F, but maybe F is a dead end and the rest of the graph goes through B, you don't know unless you try.
Clarification on A*: The estimating function needs to avoid overestimating the remaining distance, otherwise it might miss a better option. If it underestimates, then it'll still work, just not as fast. (Dijkstra's algorithm is basically A* with an estimating function that just outputs a constant, i.e. "no clue how close we are".) Dijkstra's is basically "If a route from X to Y is already worse than another route from X to Y, then don't bother doing anything further with the worse one". A* is basically "If a route from X to Y, plus the shortest route that could possibly exist from Y to Z (e.g. as the crow flies for physical distance), is worse than another route from X to W, plus the shortest possible route from W to Z, then set X-to-Y aside for now. We might come back to it if X-to-W turns out to not be as good as we hoped."
Very interesting, I've seen a comparable critical path method algorithm in project modeling lecture. But of course you can also use it to navigate from A to B. Nice video and very good explained.
I don’t know why UA-cam recommended this to me, but as a Computer Science nerd I’m glad it did. The topic tangentially reminded me of when I had to find a way to cluster groups of locations in close proximity to each other on a map into a single dot with a count of those locations across different zoom levels, which led me to find and implement the Nearest Neighbor algorithm. I later saw web browser-based implementations that seemed to do the same thing but were much quicker than mine; still don’t know how they managed it.
I love the audio. "Yeah I solved this in 20 min. I was chilling with my hot young fiancé. Didn't write anything down. Just knocked it out in my head while doing curls." 😂
Just had a lecture on route planning at my University and was interested, how close this would be really. Google Maps is for sure not using (plain) Dijkstra's Algorithm, most likely Contraction Hierarchies with some sort of grid-preprocessing to improve adaptation to live traffic
if you are not tracked, there wont be up to date traffic info. if you get tracked, it doesnt use your location to do malicious things like write down your house location to databases, or hiring a hitman to your door. this is the tradeoff you have: give your data to third party but it provides you with useful service. or you dont give your data at all, and you dont get any service.
This is an adaptation to networks of an older procedure called Dynamic Programming which you should know about if you are interested in this sort of problem.
When i ask google directions in an area i know well ,it doesn't usually find the quickest or best way. Sometimes it brings you on a crazy route just to safe a couple of seconds.
All of this and i cant find "who asked" like when i heard an argument, people just said "who asked" so i tried to find every possible strategy to find "who asked", but all the strategies i found involved me eating shit But after so long, i found this video. I tried the algorithm perfectly but somehow this "who asked" guy is so mysterious i cant even find him on the google maps, so i'll end my journey of finding "who asked" and i hope that people who see my comment can continue my journey on finding "who asked"
The map provided at 2:27 shows E-G as 4 instead of 7 as mentioned in the video. I continued using that and ended up getting 46 to X. Can someone who did the same pls confirm whether it's correct?
It's also likely they are doing some caching of similar routes too, which means side streets are even less likely to be considered because it's unlikely to do a first search for a route with traffic factored in.
The shortest distance between two points on the planet is ALWAYS a CURVE... called a Great Circle Route. Highways close to that circle will, most likely, be the fastest/shortest. P.S. I was a naval navigator.
Another thing to consider is that alternate paths are provided because the maps program can't possibly know every single situation happening on the road. Google collects a lot of data and it's very good at knowing what's happening on the road but the driver ultimately can see stuff that Google can't. Maybe a crash literally happened 1 minute ago and hasn't been reported on Google maps yet. Suddenly that longer route that gets you off at the next exit might help you avoid that traffic. It's just about providing users with choices.
I saw a video not long ago that actually explains how and why google map probably doesn’t use dijkstra algorithm and it’s due to loops if you add extra data to use this is the case for electric vehicles. If you try and find how much power it will use to get from point A to point B with chargers in between so you might think to make the weight of those negative however this will cause a loop where it keeps going lower and lower meaning the distance according to the algorithm would be negative infinity which is not possible and the only way known to avoid this is to use the old algorithm. For most other cases it probably does actually use it but I thought I would just mention it.
The algorithm is the same in either case. It's just a matter of whether the metric between nodes is time or distance. You can run this with a bunch of time metrics rather than distance metrics and you will find the fastest path. The algorithm could also find the cheapest path if you used cost metrics instead of time or distance. The algorithm finds the path that minimizes some metric. That metric can be anything that relates to the connection between 2 nodes on the graph.
@@ntdscherer In computer science this is always called a "shortest path" algorithm no matter what metric is used. This is part of the "abstraction" concept discussed earlier in the video. The abstraction is finding the shortest path through a graph with metric weighted edges. The real life outcome is a fastest route, shortest route, cheapest route, or other optimized route depending on the metrics that the graph edges were weighted with.
They do not find the shortest distance or fastest route. They find a short enough route. Checking *all* path possibilities would take too long for the webpage to load.
Google algorithm doesn’t, but Dijkstra’s algorithm does find the shortest path, given enough time. It could potentially take the age of the universe, though, as you are saying.
It doesn’t. Google maps are totally inaccurate. Example, is a city south of Sydney, google has a street running right through houses. As far as shortest distance, that’s a great joke 😂
But it is the same if you want it to be the same.. depends on the abstraction you use. In graph theory it is called the "shortest path", and what does it mean in the real world depends only on what are the values (weights) that you assign to tue edges. It can be distance in km, it can be distance in minutes, it can price or the route (factoring in the terrain that affects your consumption + tolls)...
The ending caught me off guard 😭
Lol
better idea: construct a massive 20 lane highway from la to new york, and remove the speed limit
If American urban planners could design any way they liked
Or a high speed train. 🤷♂️
A high speed train would end up cost more the the GDP of the U.S.
@@ah244895source: trust me bro
@@ah244895train tracks are significantly cheaper than highways regardless of speed
I'm a trucker with many loads from LA to NYC. Simple... take the 40 to the 81 in TN exit 421, then north to the 80 and into NYC. Why? Weather and terrain.
Well, you forgot to mention that applying this same path simultaneously from the end point can significantly shorten the time an algorithm takes.
3:48 This is a surprisingly tough thing for students to get past, because in the graph you've drawn it's obvious by look that you have to go through H or G so you should head to those points immediately, but as you've correctly said the algorithm doesn't know that (and also finding such points by an algorithm feels like it would take |V|² time), and students often have trouble with the incomplete information part of programming.
What I like to do when showing the algorithm in practice is to completely hide the rest of the graph in a kind of "fog of war" : It's not just that you don't know where X is, you don't even know any of the points that aren't X or A until you've been near them. It's easier to do in manim, but you can do that with a piece of paper on a whiteboard. Maybe the shortest path goes through F, but maybe F is a dead end and the rest of the graph goes through B, you don't know unless you try.
Clarification on A*: The estimating function needs to avoid overestimating the remaining distance, otherwise it might miss a better option. If it underestimates, then it'll still work, just not as fast. (Dijkstra's algorithm is basically A* with an estimating function that just outputs a constant, i.e. "no clue how close we are".)
Dijkstra's is basically "If a route from X to Y is already worse than another route from X to Y, then don't bother doing anything further with the worse one".
A* is basically "If a route from X to Y, plus the shortest route that could possibly exist from Y to Z (e.g. as the crow flies for physical distance), is worse than another route from X to W, plus the shortest possible route from W to Z, then set X-to-Y aside for now. We might come back to it if X-to-W turns out to not be as good as we hoped."
Even the smartest mathematics can't figure this out 🗣️, shows a video of beetle juice 😂.
As a network engineer we use this algorithm regularly :) cool to see the other applications for dijkstra's algorithm
@8:29 Google bought Waze in 2013, 11 years before this video was released. But, I suppose that’s recent in geological time ;)
Freaking awesome! I didn’t get Dijkstra algorithm, but your explanation is clicked with me!
Very interesting, I've seen a comparable critical path method algorithm in project modeling lecture. But of course you can also use it to navigate from A to B. Nice video and very good explained.
I don’t know why UA-cam recommended this to me, but as a Computer Science nerd I’m glad it did. The topic tangentially reminded me of when I had to find a way to cluster groups of locations in close proximity to each other on a map into a single dot with a count of those locations across different zoom levels, which led me to find and implement the Nearest Neighbor algorithm. I later saw web browser-based implementations that seemed to do the same thing but were much quicker than mine; still don’t know how they managed it.
For future reference, "ij" is treated as a single letter in Dutch and it makes the long "I" sound.
And also I think he says Utrecht, not Tilburg
By making the path search start from both endpoints you cut the search area by roughly 40%.
I love the audio. "Yeah I solved this in 20 min. I was chilling with my hot young fiancé. Didn't write anything down. Just knocked it out in my head while doing curls." 😂
The obvious answer is that it doesn't. If you know the area, you can always find faster routes. I believe Google prioritizes clear directions.
They used to have it that if you wanted to go from New York to London you'd swim the Atlantic Ocean.
The best explanation I’ve ever watched
Phenomenal video! An even better ending lol
Well made video, thanks
they hired slime mold as a consultant...
There’s no way that man lived his life as a vegan and just recently discovered pepperoni pizza
Counting Little Ceasers Pizza as NY Style Pizza is also sacrilege
Just had a lecture on route planning at my University and was interested, how close this would be really. Google Maps is for sure not using (plain) Dijkstra's Algorithm, most likely Contraction Hierarchies with some sort of grid-preprocessing to improve adaptation to live traffic
if you are not tracked, there wont be up to date traffic info.
if you get tracked, it doesnt use your location to do malicious things like write down your house location to databases, or hiring a hitman to your door.
this is the tradeoff you have: give your data to third party but it provides you with useful service.
or you dont give your data at all, and you dont get any service.
This is an adaptation to networks of an older procedure called Dynamic Programming which you should know about if you are interested in this sort of problem.
I love your videos, please dont change your style
This is a great vid
When i ask google directions in an area i know well ,it doesn't usually find the quickest or best way. Sometimes it brings you on a crazy route just to safe a couple of seconds.
True, i've seen this also
It's pronounced Dijkstra, not Deekstra.
As an approximation, the Dutch ij is the y of English, so Dykstra would be better.
All of this and i cant find "who asked" like when i heard an argument, people just said "who asked" so i tried to find every possible strategy to find "who asked", but all the strategies i found involved me eating shit
But after so long, i found this video. I tried the algorithm perfectly but somehow this "who asked" guy is so mysterious i cant even find him on the google maps, so i'll end my journey of finding "who asked" and i hope that people who see my comment can continue my journey on finding "who asked"
Thanks for this. I could never find the right way to phrase the question for Google........... "How does Google Maps work?"
Loved this vid
The map provided at 2:27 shows E-G as 4 instead of 7 as mentioned in the video. I continued using that and ended up getting 46 to X. Can someone who did the same pls confirm whether it's correct?
Sorry for that, I tried to copy it onto the whiteboard and must have made a mistake. The whiteboard graph should be consistent with the answers.
01:00 I think Dijkstra said 'Utrecht', not 'Tilburg'
2:10 so this is why it never takes side streets
It's also likely they are doing some caching of similar routes too, which means side streets are even less likely to be considered because it's unlikely to do a first search for a route with traffic factored in.
The shortest distance between two points on the planet is ALWAYS a CURVE... called a Great Circle Route. Highways close to that circle will, most likely, be the fastest/shortest. P.S. I was a naval navigator.
I was edging throughout this video aggressively
🤨
are you still going at it?
@@burrdid the edge never stop😏🔥😱🙏🙏🙏💀🤠🤠🤠😈🙏😈😈😈😈😃👍☹️👎😔🔫😈
@@burrdid yessir😈😈😈👺😈👺😈👺😈👺😈👺👺🙏🙏😭😭😭☹️👎😃👍😱🧙♀️🔥🧙♀️🔥🧙♀️🧙♀️🔥🙋♂️🙋♂️🤠🤠🤠🤠
@@burrdid Absolutely
0:22 A great opportunity was missed to say, "Google will factor in [...] and then tell me to eat shit in under 4 seconds."
This is relevant to me becaude i just ended up olanning a route.
The other app i was using showed me a direct train route that was
2:45 nikocado avocadooooooooooooooooo
Goggle Maps RARELY find "the shortest route" or the EASIEST route and NEVER THE BEST ROUTE!
How obvious it is, it wasn’t until I heard him talk that I realised that Dijkstra was Dutch. OF COURSE! Just look at his name!
0:50 i second this
So why do map programs give you a bunch of longer options along the way?
Some are to avoid tolls, and probably just alternatives using different highways I guess. People have different preferences.
Another thing to consider is that alternate paths are provided because the maps program can't possibly know every single situation happening on the road. Google collects a lot of data and it's very good at knowing what's happening on the road but the driver ultimately can see stuff that Google can't. Maybe a crash literally happened 1 minute ago and hasn't been reported on Google maps yet. Suddenly that longer route that gets you off at the next exit might help you avoid that traffic. It's just about providing users with choices.
I saw a video not long ago that actually explains how and why google map probably doesn’t use dijkstra algorithm and it’s due to loops if you add extra data to use this is the case for electric vehicles. If you try and find how much power it will use to get from point A to point B with chargers in between so you might think to make the weight of those negative however this will cause a loop where it keeps going lower and lower meaning the distance according to the algorithm would be negative infinity which is not possible and the only way known to avoid this is to use the old algorithm. For most other cases it probably does actually use it but I thought I would just mention it.
Well it’s only meant for positive weights
@2:42 Nikocado Avocado! He used to be a skinny frutarian.
Beetlejuice at 0:44 !!!!! How can i send all of my money to you?
Glad you enjoyed the video :)
47 hours? Fastest route NY to LA is 25 hours 39 minutes...
Dijkstra's algorithm?
You seem to be saying "shortest" and "fastest" as though they're the same thing.
The algorithm is the same in either case. It's just a matter of whether the metric between nodes is time or distance. You can run this with a bunch of time metrics rather than distance metrics and you will find the fastest path.
The algorithm could also find the cheapest path if you used cost metrics instead of time or distance. The algorithm finds the path that minimizes some metric. That metric can be anything that relates to the connection between 2 nodes on the graph.
@@zarfmouse Right, it's just a little distracting since the algorithm Google Maps uses by default is shortest time, not shortest distance.
@@ntdscherer In computer science this is always called a "shortest path" algorithm no matter what metric is used. This is part of the "abstraction" concept discussed earlier in the video. The abstraction is finding the shortest path through a graph with metric weighted edges. The real life outcome is a fastest route, shortest route, cheapest route, or other optimized route depending on the metrics that the graph edges were weighted with.
@@zarfmouse Yeah that's fair
The old way follow the gas stations
2:27
"click this video now if you want to see more, and f-"
Apple also tracks you for the same reason.
They do not find the shortest distance or fastest route. They find a short enough route. Checking *all* path possibilities would take too long for the webpage to load.
Google algorithm doesn’t, but Dijkstra’s algorithm does find the shortest path, given enough time. It could potentially take the age of the universe, though, as you are saying.
It's like rats v humans in a maze. Rats actually use Dyksra's algorithm, Humans (with a sense of direction) use the latter heuristic method :-)
The best solution is to not start at LA or go to NY.
What happens if you tell Google Maps to eat shit.
Why do Brits always say "Los AngeleEEs?" Are they all from LondOOn? From Britaane?
I never noticed before, but I guess you're right. Los Angelis
Too fast...
Except for the body shaming an excellent presentation.
It doesn’t. Google maps are totally inaccurate. Example, is a city south of Sydney, google has a street running right through houses. As far as shortest distance, that’s a great joke 😂
Noice
Shortest and quickest are not even remotely related... sheesh
Same algorithm, different path weights.
Fat jokes? Really?
Yes
You ask me whats the shortest path from LA to New york? Go to LAX, get on a plane, fly to new york, and then eat shit :D
Poorly explained. The shortest path is not always the fastest one and the presenter continuously uses both terms as the same.
But it is the same if you want it to be the same.. depends on the abstraction you use.
In graph theory it is called the "shortest path", and what does it mean in the real world depends only on what are the values (weights) that you assign to tue edges.
It can be distance in km, it can be distance in minutes, it can price or the route (factoring in the terrain that affects your consumption + tolls)...
first!
You’re very smart . I can’t speak maths, but I can spell.