Dijkstra's Algorithm : A Quick Intro on How it Works

okay in this video I'm going to do a quick explanation of Dijkstra's algorithm Dijkstra was a Dutch computer scientist so hopefully I know I'm not pronouncing the name exactly correctly but hopefully it's close enough what we're gonna do is we're gonna find least cost paths and a given graph so you can think about these graphs again you know maybe there's a cost in shipping goods from one point to another and I'm probably going to talk about in terms of distances just because that's the way I thought about it so instead of saying costs I'm just going to use distance but hey we'll do is we'll start with some vertex and I'm going to start with vertex a and I'm going to figure out the cheapest or the shortest route the shortest distance to get from vertex a to vertex H so we have all these distances between our different vertices we've got vertices ABCD efg and H so the numbers along the edges are the the distances between those vertices so again I want to find the shortest path to get from vertex a to vertex H and again I'm just gonna run through really quickly how this algorithm works so originally Dijkstra put so okay so we're gonna label little distances from vertices to other vertices along these paths so starting at vertex a I'm gonna label above that a distance of zero since that's the starting point so Dijkstra put infinities initially above all the other points b c d e f g h all those other vertices aren't it's gonna leave them blank so what we do is we start with some vertex we start with our initial one so I'm gonna kind of shade it a little bit green to say hey that's where we're starting and then what we do is we start at that vertex and we look at the distance to all of the adjacent vertices so the distance from vertex a to vertex B that's going to be a distance of three so above vertex V D I'm gonna just write the number three and let me try to shade that in a little darker I'm using a pencil for once because I'm gonna be erasing things so that's got a value of three the distance from A to C well that's a distance of four so I'm going to put the number four in front the the vertex C and then from the vertex a to vertex D that has a distance of seven so I'm gonna put a seven above the vertex D so we've now traveled from vertex a to all of the vertices that are adjacent to it so we're now done with that one so I'm gonna kind of just go back and cover color it a little bit red just to remind myself that we've we've done that one so what I'm gonna do next is okay so I've got these these vertices I've got three vertices in this this case I'm going to go to the one that has the the minimum value so we set the value above B is three above C is four above D is seven so I'm going to start with vertex B and now what I do is I play the same game I travel to the adjacent vertices I'm not gonna backtrack in this case we don't need to do that so okay so now we're working with vertex B and now what we're gonna do is we're gonna take this value that's above it which in this case is three we're gonna add that to the length along each path and so let's look from B to C so notice if we take the original value of three plus one that's going to give us a value of four and since if the value you get is smaller than the original value you change it to the smaller value because again that's gonna indicate that you've found a smaller path so if we go from A to B and then decieve well three plus one is gonna be four so we don't have to change this value because well four is the same as four let's look as well so if we go from B to F so the the value above vertex B is three if we took three plus five that's going to give us eight we don't have a value labeled for vertex F so above that we're gonna label that with a value of eight again indicating that so far we found a path of distance eight units that will give us the vertex at half okay so now I've taken care of vertex and B let's look at vertex C next so this okay maybe this one to be a little more interesting so from vertex C to vertex D well the value above see the value above vertex C has a value of four or again indicating that we found a path of length for to our vertex C well 4 plus 2 is going to be 6 if we travel to vertex D well 6 is smaller than the original value Pat the original path length we found at 7 so now I'm going to update this instead of putting out the number 7 above the vertex D I'm gonna label that with a value of 6 indicating again we found a shorter path length because now I've gone from A to C to D that's gonna be a little bit shorter let's see the other vertex we need to check if we go from vertex C to vertex F well let's see the value above C is for the path length is 6 4 plus 6 is going to be 10 well we've already found a path length of 8 so we're gonna keep that original path length of 8 2 vertex F so I'm not gonna update the value above vertex F so I forgot to put my my green that we were using that one and now we are now finished with vertex C and we're again gonna just do this so again we're trying to find the shortest length shortest length from vertex a to vertex H that was our start and our finish so let's just keep going here we'll go a little bit faster so let's work with vertex D okay so from vertex D if we go from vertex D to vertex G so the pack we found a path length of 6 the vertex D the path length from D to G is another 6 well 6 plus 6 is 12 so I'm gonna put a 12 above G likewise we can travel in my graph from the vertex D to the vertex C we knew there was a path length of 6 the new path has a length of 3 so 6 plus plus 3 is going to give us a length of 9 so that's the value I'm gonna give about of a birth vertex E I'm having a hard time talking here so let's see we've now taken care of vertex D and again let's just keep doing this so I'm looking at the the vertex with the smallest number above it we've got 8 9 and 12 so let's travel to vertex F so from vertex F so now we're working on vertex F to go from vertex F to e well that would be a path length of 8 plus new path length of one ok so again that's going to tie and keep us at a path length of nine and then if we look from we can also travel from vertex F to vertex H so we had a path length of eight this new path has a length of eight as well so if we travel from from F to H it says we've now found a path length of 16 and again I've now taken care of vertex F so we're done with that one let's see so we've only got two vertices left we've got a and G so let's look at vertex E so that's the one we're now working on so if we travel from E to vertex G 1 9 plus 3 that's going to be the same path length of 12 and now we've also got from we knew that there was a path length of 9 to vertex e notice if we travel along this direct path from vertex a to vertex H well we knew there was a path length of 9 this path has a length of 4 9 plus 4 is going to give us a path length of 13 so we've now found a new shorter route so let's update that value so we found this new shorter route to be a path length of 13 and now we've taken care of vertex E and last but not least let's look at vertex G well the only thing left to check is from G to H we knew there was a path length of 12 we'll add to that a path length of 2 that's going to give us a total path length of 14 which is greater than the original path length we found at 13 so we've now checked in vertex G as well which means we found our shortest path length of 13 so we know that there is a path of length 13 units that goes from our original vertex a to our stopping vertex H so that's all there is to it you just are just basically updating path links as you go on there's a lot of terminology involved with some of this stuff you know I'm sure if you're taking this you're probably in a discrete math class probably more likely in a computer science class you know go check on Wikipedia for example there's a lot of the terminology you may need but this is just the basic idea of how the algorithm works

Channel: patrickJMT

Views: 101,578

Rating: 4.9225807 out of 5

Keywords: Dijkstra's Algorithm, patrickjmt, patreon, least, cost, shortest, distance, minimum, minimize, computer science, algorithm, graph theory, discrete math, mathematics

Id: eFZCPlZCyIM

Length: 8min 54sec (534 seconds)

Published: Tue Oct 17 2017