Skip to main content
Loading Explore guides…
Dijkstra's Shortest Path · Acedra
Home
Explore
Computer Science
Dijkstra's Shortest Path
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
25 segments
Copy
Hide video
0:00
(Sean:) So what we got here, Mike, tell me, tell me! (Mike:) Well, we have a strange graph drawn out on my page. A comment on a previous video asked about Dijkstra's shortest path, now I happen to have implemented Dijkstra's shorter path for one of the pieces of research I was doing a few years ago, so I thought: "I'm at least somewhat placed to have to give an opinion on it!" So let's talk about Dijkstra's shortest path, what it is, where it's used, and so on.
0:24
Path finding algorithms are obviously quite important -- we use them all the time on Google maps or on our sat-nav system, all right, there was a recent video on satellite navigation and how it works, but of course that's only half the story. (Mike:) Finding out where you are exactly is the first part of the problem, the second part is "I want to go over here, what's the best route to do this?"
0:44
Okay, route planning also comes in on things like routing, so if you've got a network and lots of routers what's the best way to route those packets through which ports to get to your destination the quickest, so things like this -- now Dijkstra's shortest paths sees a lot of use in all of these things and extensions of it, so for example A* search -- so I've drawn out an approximation of a road system on this piece of paper, so we're going to use the analogy of roads
1:10
for this one, because I think it's a good -- good example of types of shortest paths and we're trying to start here, at S, and get down to E, right, this is broadly speaking, a small version of what a sat-nav does when you say: "How do I get there", right? Now, each of these nodes represents a junction, so, the vertices on the graph, so, A could be a roundabout, B the T-junction -- doesn't really matter --
1:34
actually B is more of a roundabout because it has four outputs -- anyway, each of these numbers represents how hard it is to get along that road, so that in real life would be whether it was a motorway or a highway, whether it was a country road with a load of potholes, maybe there's a tree down it and so you can't get through that road, right, so in the Dijkstra implementation that I am familiar with, and most Dijkstra implementations,
1:57
smaller is better okay, so broadly speaking this route here is kind of like our motorway right, twos, ones, that's good, this one is a bit of a faff, you know, for some maybe mildly A-roads, right, and this seven here that you're falling in a fort, and, you know, you've got water in the engine, and it's bad. The question is "how do we find a route from here to here", now, of course, this is a small graph so actually what we could just do is just search all the way through it by hand or
2:25
using a very simple sort of brute-force search approach, and kind of get the best go, right, but if you think of the UK or the US or some other countries' massive road network, we can't afford to do that, right, we have to be a bit smarter about how we look through. And we also want to know absolutely that once we found a route, it is in fact the shortest route, and we didn't just miss one. What Dijkstra does is basically
2:49
similar to a sort of brute-force flood-fill search through this space, but does it in a kind of -- in the order that makes the most sense, based on how fast these roads are, so it will check the quickest roads first. So to do Dijkstra, we need a few things, first of all we obviously need a graph right and then we need some -- some idea of how long the path is, to let's say B, once we've calculated it or something like it so at the very beginning of our search we have S, we are at S,
3:16
(Sean:) As for start, right? (Mike:) It's for start, yes, which confused me because some of the other letters are just in order and then these two aren't, but anyway, S has a distance of zero, right, it costs me nothing to get to S because I'm already there, everything else -- I'll just put a couple out, just to show you, A, B and K have a distance of infinity because that basically says we haven't looked yet, we don't know how far, so for all we know it might not be possible to get there,
3:38
no, and finally, E it's just the same, it's infinity, but with a smiley face to say that we've made it, right, now this structure here that I'm going to create is called a "priority queue". Each of these will have a distance, but they're ordered also by that distance, so the shortest one is at the top, that's important, and we'll do it as we go through. So let's start our search, we start at S, and we look through the neighbors of S and we say "right, well, A,
4:03
it costs me 7 to get to A", right, it's a bit of a pain. So, we were at 0 distance, it costs me 7, so now we're at 7, right? So, A, I scratch my infinity, and I write 7, all right, so A is 7, okay, A is still the second shortest path currently because all the others are infinity. Yeah, B is 0+2 so that's 2, so let's just put a 2 in there. (Sean:) This is all even though we haven't actually got to the end yet, you're just looking at the numbers.
4:31
(Mike:) we can't get to E without having a look through all of these junctions, so this is what we're doing, and we're working our way in a smart way, now B is in this priority queue, but it has a lower number than A, so it takes its place at the top of a line, okay, so that's good so far. Finally, the only other thing connected to S is C, which has got a weighting of three, so let's just find C in my list, of course, shuffled thingies and there we go, and hopefully
4:56
how Dijkstra works will start to become clear once you see what I do next, so C is three, the only other thing that of course I forgot, is while we're doing our search, we have to keep track of where we've been, so B, for example, we know has a distance of two through the path S, ok, so S was the previous version, right, that's also true of A, and also true of C. Now after we swap
5:20
C and A so now we have them in order, all we have not seen is still infinity. Now, S is done, right, so we can take it away and put it in our finished pile over here, right, S we don't need to worry about anymore. The next step, is to see where is the current shortest path, well it's B, right, B has got the lowest number, so let's start looking at B. So, if we look at B, we've already been to S, so we ignore it. We can go to D,
5:42
so let's put in a D, and D is the distance to B plus whatever this road is which is 6, 2 plus 4 is 6, and the route through D, which is shortest is currently going through B, and we'll put that in, now 6 goes in just above A, ok, there we go. Now we can also go to B from A -- we haven't finished with A yet, it's just sitting in this queue -- and currently the distance to A is 7, right, but, actually, the distance to B was 2, and the distance to A from B is 3, which is 5, so actually,
6:12
taking this detour here which looks longer is actually shorter, because of this tree on the line or something like that right, so remember, you know this isn't representative of the actual physical distance from S to C. So we've updated D, and A is now shorter, right? So, we kept -- we take our A, and we say "well now the route is 5, not 7", it's decreased and it's no longer the shortest path from S to A, it's from B,
6:35
so look scribble out S, right, like, I'm getting too much technical needs but don't worry about it. So, A now overtakes D in our priority queue, all right? So that's looking good, okay, H, B had a length of 2, H has a length of 1, so H has a distance of 3, B is done, right? We've done B, we can count that as done, so C next, right, so we're here. We can't go to S, we can only go to L, that's a nice, easy one. So I need to find out -- so L goes to C and
7:05
it's 3 plus 2, it's 5, so L comes in just underneath value like this, so C's done So we look at H, and we say "what's next from H". We can look at F, so F will get 3 plus another 3, so about 6, via H, and then G is H, which is 3, plus 2 so that's 5. A next, we've already been to S, we've already been to B. So we start to get a little bit faster now, we've seen some stuff, already. What we're basically saying is, we know what the shortest path to B
7:32
is, because we've already seen it so we can only look at new things, so we look at D, D is currently 6 via B, A is currently 5, 5 plus 4 is 9, which is bigger than the old D, so we make no change, the shortest path to D does not go through A, so we don't worry about that, ok A's done. Next up: L. L can't go to C, we've already been there, I and J both have a length of 4, so that's just fine, those two I and J -- [I'm] needing all of them --
8:01
right, so these both go through L, and they both have a path length of 9... 9 okay, so these go -- and they're both long, but they go in front of all the infinity ones. But -- but down at the bottom here all right, the order isn't important. So how [are] we doing, L is done, so then you can see what's about to happen, right? We start with G, G has got a distance of 5, we've already been to H, let's go to E, and so we say E goes back to G and
8:27
has a length of 5, 6, 7, and we're there, right? And then the final step is just to backtrack our route based on where we've been, so E goes to G -- we can skip these, they aren't used -- G goes to H, H goes to B, and B Goes straight to S, and that is our shortest route through this graph, it's found by Dijkstra, the idea is, that if this graph was much much bigger, you would prioritize looking down motorways first, because they have less weight, and you would
8:56
prioritize physically short distances, anything that you can to try and make your search a bit quicker. When you're searching to let's say travel from Nottingham to London, you don't look at the roads in Scotland, at least not first, Because it's unlikely [that] they're going to be the shortest ones. What you do is you get yourself to the M1 and start travelling down towards London as quickly as possible. That leads us to one last problem with Dijkstra, which is perhaps for another video?
9:18
But I'll just -- I'll just introduce it -- if you imagine a situation where I'm at my house, and let's say my house is here, at S, and this is sort of [the] M1 junction, right, which happens to be about junking 26? But we'll call this A, alright, and then this is where I'm going in this direction, so lots of nodes along here, and there's lots of nodes along here. And this is my destination down here on the end of this motorway. Because of a slight traffic jam,
9:44
these all have slightly higher weights than these. Because Dijkstra doesn't build any idea of the direction you're traveling, any kind of heuristic about what you're doing in a sort of smarter way, it's going to look up here first, it's going to travel all the way up this motorway as far as it can and only change direction when it becomes the shortest path to do so, so what you need to do if you're going to actually implement a sat-nav, is be a little bit smarter -- don't start sort of
10:09
looking to all the fast roads, look at the fast roads that are going roughly in the right direction because otherwise you might be wasting a lot of time.
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