LOADING ...

Dijkstra's Algorithm - Computerphile

580K+ views   |   12K+ likes   |   205 dislikes   |  
10:42   |   Jan 04, 2017

Thumbs

Dijkstra's Algorithm - Computerphile
Dijkstra's Algorithm - Computerphile thumb Dijkstra's Algorithm - Computerphile thumb Dijkstra's Algorithm - Computerphile thumb

Transcription

  • (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.
  • 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?"
  • 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
  • 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 --
  • 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,
  • 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
  • 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
  • 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,
  • (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,
  • 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,
  • 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.
  • (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
  • 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
  • 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,
  • 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,
  • 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,
  • 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
  • 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
  • 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 --
  • 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
  • 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
  • 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?
  • 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,
  • 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
  • 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.

Download subtitle

Description

Dijkstra's Algorithm finds the shortest path between two points. Dr Mike Pound explains how it works.

How Sat Nav Works: /watch?v=EUrU1y5is3Y
Slow Loris Attack: /watch?v=XiFkyR35v2Y

http://www.facebook.com/computerphile
https://twitter.com/computer_phile

This video was filmed and edited by Sean Riley.

Computer Science at the University of Nottingham: http://bit.ly/nottscomputer

Computerphile is a sister project to Brady Haran's Numberphile. More at http://www.bradyharan.com