Skip to main content
Loading Explore guides…
Dijkstra's Algorithm Problems · Acedra
Home
Explore
Computer Science
Dijkstra's Algorithm Problems
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
33 segments
Copy
Hide video
0:00
In the last video, if I remember correctly 'cause it was a good month ago now. I drew a graph out and we worked through it with Dijkstra, and at the end I pointed out a couple of problems. So let's just remind ourselves about those problems and then when we'll talk about A star we can see how it addresses it. The problem is with Dijkstra that it will follow the path currently shortest and that -- and doesn't pay any attention to what direction it's going.
0:24
So if i'm coming down here to my end goal, and I'm starting up here, that's fine if the weights are all the same because it will look at it up here and there, but I'll get there quite quick. The problem is of course if you've got the map of the UK and it's searching quickly down all nice motorways when in fact actually we don't need to go down the motorways because it's a country road drive or something like this. Now, course in practice, it wouldn't take very long
0:44
still because your computer is quite fast but the whole point of these algorithms is they're quick and you can imagine if you're writing a sat-nav, you don't want it to take a long time churning for the roads unnecessarily. The other problem is, if your graph doesn't look like a map because, you know, in some sense the UK road network isn't quite sparse but the most of the country doesn't have a road on it. It's mostly fields and sheep and stuff. But, you know, all houses. If you have a
1:11
situation where you've got a quite a dense network like this, so I guess you could say a bit like Manhattan. But also just, you know, another problem where your graph structure is different. So if you're looking through an image or something like this. I'm starting up here and cross that out. There we are and I'm finishing down, I don't know... here. Let's remember that Dijkstra follows the shortest path based on the distance of each of these. Now, if it is just a uniform grid, let's
1:37
say, we have no interesting information to provide for these weights and all these weights say one so it's just gonna to flood fill from here. It's gonna go here, and then here and then to these three and then to these four, and so on and that's not very optimal. Especially if we just literally want to go straight down here, like this. So we want to build in some kind of idea of, but not necessarily the direction we're heading but we are at least going towards our goal, so we can
2:02
aim for it. And that's what A star does. A star is basically a small extension to Dijkstra that builds in a heuristic that says we're getting a bit closer. This is our nice screwed up graph from last time and this is our nice new fresh graph that I've done which is, topologically exactly the same. I may have traced it. So, we could do Dijkstra on this. I've got my little cards for my priority queue. I've reminded myself how the end condition is so I can end it properly.
2:30
That's all fine. What we want to do is extend this to A star. Now, A star is basically exactly the same as Dijkstra, except it has an additional heuristic that is how far do we have to go. And, in this case, a pretty reasonable heuristic to come up with will be literal Euclidean distance of how far we have to go. So, in this case S to E will be that far, C to E will be that far. And so on. I couldn't think of a good way of calculating this without literally just
2:56
measuring it. So I got my, got my... dainty 10 meter tape measure, which is a little bit overkill. But we'll, you know, make it work. So this is all a bit odd. I don't use tape measures as much as you can imagine 'cause I mostly sit at a desk and do typing. This is a tape measure in centimeters and inches. Let's use inches today. Alright. Imperial, woo. So I'm gonna literally measure the amount of inches from S to E, and then A to E, and then I'm just gonna put
3:26
this on here now. And this is where you fast forward. So, I'm gonna use it, the black pen for this. So let's say this is 10. There. This is harder than I thought it would be. I haven't got enough hands. 8... 6... I'm rounding up a bit it's not very accurate. 4... So the green ones are our step distances from Dijkstra and the black ones are measured inches. Also 3, 6, 7. We're getting there. 6 again. Alright. That's me doing my workman's... Now:
3:58
we've got exactly the same graph as before but now we have some measure of the distance to our thing. It's not a very good heuristic in a sense that my measuring is not very accurate and for A star to work really well, you have to have a consistent metric and you have to, not overestimate how far you've got to go. Things like this... But, we'll just hope it works, sort of work itself out.... You know, it can't be any worse than me you know, doing it by hand anyway. So, recall
4:24
when we did Dijkstra. What we had was we had some queue here like this. These had the current distance from the start to these nodes. And if one of the nodes had a shorter path, it would move up the queue and then when we wanted to expand a node we take it off the queue. A star works exactly the same way, except the distance isn't what we ordered them by anymore. It's a distance of the path plus how far they have to go. so for example. B, the distance is going to be 2 plus 7 which is 9. Alright.
4:53
So B will have a value of 9 on this queue. And the idea is that if something has a long way to go, it's going to receive a higher weight and be further down the queue and expanded later. What it will do is prioritize nodes, that are going roughly in the right direction, unless... I mean it will still go down really good paths, really short paths. But not at the expense of everything else, it's the idea. OK, so let's run through this just like we did with Dijkstra and hopefully I won't make
5:18
any mistakes. People will very kindly point them out if I do. Oh look, look. Checkered flag. This is why I don't draw things, because it's not it's never good... Right, okay, we're starting at S. I'm not going to draw the infinity symbols on because we know that all of these nodes start with a distance of infinity because we don't know how far the path is. In Dijkstra, we store the distance to each path, and we also ordered by that distance. We've now got two separate measures we're
5:43
measuring in A star: one is the distance to the node, and one is the distance to a node and any remaining distance. So, we kind of need to have two values on each of these things. So I'm going to try and keep the colors the same so that we don't lose track. So anything I draw in green is going to be this 'g' cost function which is the distance to a current node, so for C that would be 3. And then, in black I'm going to have 3 plus 8 which is the sort of combined
6:07
cost; the thing we're actually ordering by. OK, so the path cost to S is 0 and the sort of distance to go is 10, but it won't matter because S is the only thing in our queue. So we'll put S in the queue but everything else have a distance to infinity. So let's start expanding some stuff. So A first. A has... I gotta find A mate. Fast forward. Oh here we are. Why aren't these in alphabetical order? I mean, you know... What was I thinking? Right, so A has a distance of 7 and a combined
6:35
distance of 9 plus 7 which is 16. The same for B. Same B, B, B... Again B. I mean it's actually at the end. Unbelievable. So I'm gonna keep seeing it at the top now 'cause I know that's coming. OK, so B has a weight of 2 and a combined cost of 7 plus 2, which is 9. So, I'm gonna put that in there. Now, B goes in the queue and goes ahead of A, because 9 is smaller than 16, right. We're keeping a track of these green distances. We're not actually using them to see which one
7:04
comes next. And then C. C has a path cost of 3 and then a combined weight of 11. 8 plus 3. And then that goes in just above A like this, right. So actually, so far, pretty similar to Dijkstra, apart all the numbers are changed. So what's next. We start expanding B. I haven't been keeping track of the previous node so all of these currently there's the storm in red all are going through S at the moment. OK, so B next. We can go to A. A has a distance of seven when we deciding
7:35
whether the path to A better via B we don't care about this heuristic, we only care about the actual cost of it, the path to A, so in this case 2 + 3 is less than 7 just like with Dijkstra we're going to replace it so A, its new weight is going to be 5, and 16 is going to be 5 + 9, so 14, right? And this now, this path is going through B, not.. Do you think I can turn this into a B? Oh yes, there we go, look at that. So it stays below C, it's not a big deal.
8:06
OK, D... Let's find in my shuffled list. If you're implement this, don't shuffle it because it'll be a lot harder to find in memory Right, there we are. B has a path length of 2 D has a path length of 4, so that's a path length of 6 and D has got a distance of 8 to the end so actually you can see here that D is traveling forward in this direction, but is actually getting further away than B so these going to be quite heavily penalized that's our hope so D is not going to be
8:32
expanded for a while we're going to look there until it's a last resort So 8 + 4 is 12, and that path goes through... You know what, I'm just gonna leave the lids off. And that goes through B. So put that in. And that goes above A because A is a terrible one, remember there's a fallen tree on that one, but it still could be back and then finally H. Now, H has a path length of 1 which is nice and quick, B has a path length of 2 so the total path cost is 3 and the
8:59
actual heuristic cost is 3 plus 6 which is 9, that's 9 in here, 9 is looking pretty good right now. Now H goes straight above everything like this, right? B is about to pop out so that's good. So B is finished, and we put B on our finished pack. Huh, finished stack... Finished list? Finished data structure over here. Next up is H, right? Now, last time we didn't expand H next, we expanded C next in Dijkstra because they had the same rough paths cost which is 3 and C was already in the list so
9:28
now we already started to move a little bit faster with A star which is good because it means my example is working so H comes off and let's see where we can go we could go to F, so that's easy, I'll find F F has a past of 3 + 3 which is 6 and it has a distance to go of 6, so that's a total heuristic cost of 12 and it's going through H. Right, this goes in and it will come in behind D here with a path cost also of 12, right, in general if there's a conflict will just put the first on in
9:57
you know, depends on your implementation G has a path cost of 3 from H plus another 2 so that's 5 and then plus another 3 is 8. Ok, we're done with H G goes in right to the top which is good news for us, for our nice elegant search. So we're going to expand G, so where's E? But I'm not gonna go off half-cocked this time and finish my algorithm here. G has a path length of 5 and so E has a path length of 7 see now I've drawn this checkered flag and it's in the way of my numbers, thanks for
10:25
the suggestion there. Right, E has a heuristic cost of zero because we're at the goal so actually 7 is the final value that we get given here and this goes through G and we're going to put E in, so E goes in here G is not really on the stack anymore. G can't expand anywhere else, we've already been to H and so the next iteration of the algorithm starts, right? We popping off the top we're about to expand it and we realize that's where we're going and we finished our algorithm
10:53
ok so then just like before we trace back through so E goes to G and then... Where's my G? There it is. And G goes to H, and then H goes to B, and B goes to S, and S is the start, alright? So we've got our path, S-B-H-G-E Now in this case it's exactly the same path as Dijkstra because I picked a fairly reasonable heuristic, right? Plus or minus a bit of my dodgy measuring But you can see we didn't bother to expand C or L or even consider I and J many fewer
11:24
nodes got put in the stack...In both terms of the amount of computation we did and the memory footprint was reduced and we still obtained the same result. So there were one or two comments on the last video about not expanding those but you're saying that on A star you definitely don't have to expand those, No. The comments on the video were because basically I forgot to wait until E was expanded to finish, I got overexcited and as soon as I saw E, I declared it over when we went and got
11:48
coffee and yeah and that's not right because technically speaking there could have been a path from say, F to E, that was super-sneaky and really quick, right? I'm sorry, super-sneaky is not a technical term you see in the literature, and if that had happened we have to wait until E bubbles to the top of our priority queue to be able to know for sure that we've got the shortest path. In this case it was very straightforward, E went straight to the top, but you can never guarantee and a
12:11
different graph will have a different thing so the actual stopping criterion for both Dijkstra and A star is when your goal node gets to the top of your priority queue. But yeah that was good that people pointed that out because it completed the video with a bit of extra comments. To wrap up you can imagine now that we've seen a video on how that works in terms of GPS positions and we've seen a couple of videos on pathfinding and there's lots of videos on data
12:34
structures in this you can imagine now that you might start to think i can actually not see how that might be implemented I could see you know the parts of the system that have to work together we've got a map that stored in the memory we've got nodes that we're trying to get to and from, that we've got an algorithm that will find a way through Now, you can imagine also that it's unrealistic to expect a small sat-nav to completely compute its way through the
12:59
UK but if you saw "I what the best path from Land's End to John O'Groats" you might melt your sat-nav unless you do something a little bit smarter so you can imagine they might precompute some of these things but they know the shortest way of getting from Nottingham into London is via the M1 or something like this to sort of hard code some of it in some sense to be honest I don't work for a sat-nav company, I don't know what their proprietary algorithms are, but you can see this is the kind of
13:21
thing we're doing we're trying to find a nice elegant way of getting from A to B and there's lots of pathfinding algorithms and you could come up with lots of interesting heuristics, not just euclidean distance
13:33
Also of course they're going to have a GPS to measure up in your dating that I mean yet although i would say VPS often has an accuracy of possibles few meters so it was shoddy measuring tape is actually pinpoint precision compared to that still have maps are carefully crafted would be exact known positions of all these junctions and they know how long it takes to travel out the roundabout and they know how long it takes because of traffic and think about this they're going to be doing a lot
13:56
smarter or albums and i'm doing but this is a start and you can see you could build this up into a really good system
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat