Dijkstra's Algorithm vs Prim's Algorithm

in this video we're going to be drawing a distinction between Dijkstra's algorithm and prims algorithm so these are both greedy algorithms that operate on graphs prims algorithm tries to find the minimum spanning tree in a graph and Dijkstra's algorithm finds the shortest path tree so given a start node we're going to find the shortest path to every single vertex and we're going to keep upper bounds of paths and continuously try to improve them these these are both greedy algorithms they vote up or operate on graphs they both create trees but at the end of the day they're they have different goals and their greedy strategies optimize for different things so we're going to perform both of them on this graph and we're going to draw that distinction and make it really clear first off we're gonna use Dijkstra's algorithm and the way Dijkstra's algorithm works is we're going to keep a table of distance upper bounds and each of these upper bounds are the shortest distance from the start we're going to make the start a the shortest distance and continuously we're going to try to improve these as we go through the graph and we're also going to keep track of the parent this actually is a parallel you can draw to some dynamic programming problems a lot of questions people have is how do you track the optimal problem because sometimes you just find the number solution like the maximum weight of a knapsack or something the way that you would do that is you need to keep track of the winner at every optimal step we would need a table to keep the parents that had an optimal solution so we're gonna create that table so the way that Dijkstra's works is we're gonna take the start as a and as we're going through this you're gonna see the distinction we already drew the distinction which is the greedy choices are different but it becomes really apparent as we go through both of these and there's a lot of great resources to learn about both of these algorithms Dijkstra's and prims with the complexity analysis so I don't want to go too deep into that I'm just trying to draw the distinction here we're going to add the first vertex and we're going to mark the distance upper bound is 0 and then for every other vertex we are going to give it a distance upper bound of infinity we don't really know how far that vertex is if at the end of this search the distance is still infinity that means that the item that vertex was not in A's connected component if it's outside of his connected component then we can't reach it to find its distance to a so ultimately we can never prove that so it'll stay in to infinity and now we're going to mark all of these vertices as unexplored and what we're going to greedily do is we're going to process the vertex with the smallest upper bound on distance that has not been processed so none of these have been processed and the smaller upper bound distance is the a itself which is the start and it was set up this way so we're going to process that vertex so now we're processing on the a and what we're ultimately going to do is we're gonna look at every single edge coming off of a so we have one two three four four edges coming off of a and we're going to see if I have a as the parent will I improve the distance upper bound to any of these vertices coming off of the a so is the distance to a we're gonna look at the first vertex B is the distance a plus the edge weight to B which is two will that give us a better cost than the current upper bound the current upper bound on B is infinity so 0 plus 2 is 2 and the min of 2 and infinity is just 2 in fact it's actually a good way to go we want to come from the a so we're saying if I want to get to be the best way to get to B right now is a so I'll mark the parent of B as a and then the new upper bound on B is going to be what we yielded as the minimum here which is just 2 so given that I choose the best path to be the worst case work that I do in terms of cost is going to be 2 so now we can process the C and we need to make sure we process all of these vertices process the C what is the current costs to get to C infinity can we beat that by going through a what's the cost to get to a at maximum at 0 so 0 plus actually traversing the edge weight we're looking at C so we're gonna do 4 so 4 so that's just 4 and ultimately the minimum of 4 and infinity is 4 so it's a better choice to have the parent or the node that comes above force C in an optimal path have a included so a is going to become C's parent and the total cost our new upper bound on a best path to this vertex is going to be 4 and you were going in alphabetical order for these vertices so we see D now we're gonna do the same thing what did we just do there so we know that the best we can do to get to a is zero plus the edge weight 2d is seven versus the best we've done so far to get to D which is infinity so the winner is going to be seven so we want the parents of D to be a and then we want to mark the new best upper bound to D as seven okay and then we're going to look at a 2f a 2f what is f best upper bound so far infinity what are what's the best cost to get to a zero and then the edge do forcing the edge is 5 0 plus 5 that's just gonna be 5 we can just see that a is the better choice so we want Epps parent to be a and then the best upper bound we now have is 5 ok and that was the last that was the last of her text to process on a so now we mark a as finished so ultimately what our goal is off of each vertex we want to say from this vertex can I improve all of the upper bounds for all of the adjacent neighboring this vertex if I can I'll update the parent and I'll update the new better minimum upper bound and if I do this for the whole tree and every time I inspect a vertex I guarantee I've already found the best way to that vertex the start we already know the best way to get to the start which is doing nothing because we start at the start if we hold this rule across the whole graph we're going to generate a globally optimal solution next Dijkstra's will choose the unexplored vertex that has minimum cost so right now that is going to be the B and as minimal cost it has not been explored ok so B's a distance best upper bound to be is 2 how did we do that we came from the parent of a and because we came from the parent of a that means that will we traverse that edge and we decided that was the best choice who where B's edges we have four edges coming off of B we'll inspect all of them and we're going to try to improve our upper bounds using those edges we're gonna look at the a first so we'll say min who's the winner here we're going to say what is the best to get to a it's going to be 0 now we're going to compete that against what is it cost to get to B from the start to plus the edge weight which is 2 and then 4 so we see it's not a good choice to go through B for this path because ultimately we're actually going to just go to B and then come back that's not a good way to get to a it's better just to stay at a so this is kind of redundant but it's still a checked algorithm will make depending on how we implement it so we didn't do any updates there nothing was improved and now we're going to look at D does this improve up an upper bound the best distance to D as of right now is seven and then what's the best distance to get to B it's two plus the edge weight the edge weight is going to be six B to D is 6 6 plus 2 is 8 and then the minimum of 8 + 7 is 7 so we see that it's a bad idea to have the parents of D be the B because if the parent of D is B B's parent is a so we'd go a B D that's a path cost of 8 the path cost of a D is just 7 so it's better not to take that path we didn't improve anything so now we're going to look at the e what is the best way we can get to e right now it's infinity and then what is the best cost to be it's 2 and then what is the edge weight between B and E this is the cost so on top of the cost to get to be the best cost I found I need to add the actual edge weight so that's three so now I have 5 so it's actually a better idea to go through the B to get to e because we never even reached it so the parent of e becomes B and the new distance of our bound to beat is 5 and then finally we need to look at the G so we're gonna look at the G so we need to compare infinity versus using that B as a parent if we use the B as a parent it's 2 plus the edge to G be it a G is 8 so do we make the choice to go through B yes we do because this is 10 and what do we do we mark B as the parent of G and then the distance upper bound becomes 10 okay so I think we explored all of the vertices off of B now we need to mark B as explored it's we're finished and now Dijkstra's is gonna choose the minimum again of the unexplored vertices the min distances so so far the minute the minimum distance turns out to be C in this case so we're gonna explore off of C now so we have two edges coming off of C we're not gonna backtrack to the a because we know that's just redundant the actual if we code this in a normal implementation we would check that edge ultimately because it's a normal edge we're gonna loop over the edges but that's not going to do anything for us so we won't check that min but we could improve our upper bound to F so we're gonna try that so the cost to F right now is five and we want to see if we can improve that so going through C so the costs to C is for right now if we made the jump to F it would be six and ultimately we see that 4 plus 6 is 10 going through the C would not improve anything in terms of jumping to the F we wouldn't want to jump to the F through the C we could just go AF so we're not gonna take that there's no more edges to explore so we're just going to mark this as complete and then we're going to take the minimum costs vert vert X that has not been explored yet we have a tie between E and F so we'll just choose the lower at 1 in alphabetical order so we're gonna choose e we're gonna try to go off of E and prove all the upper bounds for the vertices touching e so E has two edges coming off of it we're not going to check if II can improve the path to G so we're gonna do a comparison so the best upper bound to G right now is 10 what is the cost to get to e itself that's going to be 5 and then what is the Edge cost to jump from the e to the G it's 7 so 7 plus 5 is 12 so if we do a comparison the 12 versus 210 it's better not to go through the e it's better to go through the beat we're gonna have a cheaper cost path and again this is this is the whole point of the video this is why I'm trying to get across that these algorithms are making choices differently we're gonna look at prims but Dijkstra's is making a decision where we want to minimize the path from the start we're doing that at every vertex prim has a different goal which is to minimize the edge that we add to the spanning tree we're growing and we're gonna see that and now the minimum cost vertex is going to be F so we have 4 edges coming off of F we have the C the a the D and the G can we improve the upper bound of seven so we're going to say what is the cost to get to F it's 5 the cost to get to F is 5 the costs to jump to D is 1 and so this is 6 so it's actually better to go through the F to get to D then take that immediate path from A to D so what we're gonna do is Mark the parents of the D as F and then the new best upper bound is six and now let's try to improve the path to G so the upper bound of G right now is 10 and the best we can do to get to F is going to be 5 so if we go through the edge from F to G it's 6 so 5 plus 6 is 11 so ultimately that doesn't improve anything that does not allow us to get to G any faster so we're finished processing F and now the lowest cost vertex that has not been visited is going to be D so we have four edges coming off of D so D came from F so we won't just go to D and then go back to F that would essentially be wasting time that could definitely not be shorter to get to F unless there was a negative edge weight then that would make the min cost be better because that would reduce cost that'll take away a cost of Pat's reversal but we're just gonna assume all the edges are positive so we're gonna look at a B and G so can we improve the path to a going to d the Kern upper bound on a is zero and no matter what we do the way we can get to D it'll be max cost 6 and then we'll have to add the edge weight of 7 so that'll be 13 there's no way we can be 0 because all of these edge weights are positive so a is not going to be improved so then we're at the B how are we going to improve the B the B's a tattoo right now so the cost to get to D is 6 and what is the cost to traverse the edge between D and B that's going to be 6 so we get 12 and we weren't able to find that better cost path so now we're gonna look at the G can we improve the upper bound on G which is 10 can we do that from D well the edge weights 6 and the cost forgets D is 6 so that's 12 and that does not be 10 and that finishes up all edges for D so we mark it as complete and now finally G we're gonna see if G can improve the path to anyone it's connected to and actually we can immediately just see of course we're gonna still do the for loops if this was code but we can see that we can't do that because look at all the edges coming off of G we're going to be going back and adding value what is the cost to get to G the cost is already 10 so I guess this is like the intuitive understanding if the min costs to get to G is 10 and every single one of these optimized costs are going to be less than that and we know that this is going to be positive the only thing we can do is go up in value or stay at 10 but everyone's less than 10 so logically it's impossible for us to even beat anyone in this list because all edge weights are positive we can't improve on any of these guys because getting to G itself takes 10 in cost so GE let's just market is finished and then that is Dijkstra's algorithm run on this graph these are all the shortest paths and let's actually draw out the tree because we have those parents we can climb up this tree and actually visualize it so let's create the shortest path tree so those are the nodes and when we get to prims our job will be to connect all of these vertices but in this case we just are making a shortest path tree so a has no parents B has the parent of a C has the parent of a D as the parent of F he has the parent of B F has the parent of a and G has the parent of B and let's give the edge weights to these if we did this right this should be the shortest path tree produced by Dijkstra's algorithm and again these greedy choices were made by choosing the shortest the smallest cost vertex to use next if we continually choose that then ultimately we're always going to be expanding these upper bounds off of minimum cost vertices that we're facing the next iteration of processing off of and now we're going to look at prims algorithm which has a different goal its goal is to minimize choose the smallest cost edge on the growing minimum spanning tree that we are building and this will be very clear by the walkthrough we do so it's great that we saw Dijkstra's and now let's look at prims algorithm let's see the minimum spanning tree so first off what is a minimum spanning tree we're going to take all of these vertices and just move them over so we can look at them we want a subset of the edges that is going to be minimum in cost but connect all of the vertices so ultimately we want to form a tree which is going to be a connected component and this tree is going to have minimum cost there's a lot of trees that we can create to connect these nodes but ultimately there's going to be certain trees that have a minimum cost and there might be multiple minimal cost trees so we're going to look at prims we're going to start off of the start vertex and we're going to grow the minimum spanning tree green we're going to make the locally optimal choice every time what are the edges coming off of a so what we're gonna do will will keep dotted lines is what is prim considering at every single step of the process of choice and these are all of the edges that we want to build off of a to grow the minimum spanning tree and we're going to greedily choose the smallest one and the smallest one in this case is going to be that edge of size of cost - so we're gonna connect the a and B so our tree has two nodes our tree has the a and the B we made that connection but now now that B is connected to the tree we consider all of these edges coming off of it so I want you to think of this as as soon as we add a node it adds these this it's it's just like a ray of vision because these two nodes added to this tree are going to have edges and other nodes they can see of all of the nodes that I can see from the given tree that I'm building if I choose the smallest edge every single time then ultimately we're going to build a minimum spanning tree because we're gonna expand this out slowly choosing the minimum cost edge possible at every step to add a node to this component or this tree we're building so we're gonna choose the minimum cost out of all of these which one is that that's going to be the e so we chose the edge that's the E and now we're going to consider all of the edges coming off of e what is the edge coming off of e we already took the edge be E now we'll take eg and so do you see how as this tree grows at all times we will always consider all edges that can expand this minimum spanning tree will produce the minimum spanning tree because of the way we're considering every one possible that can connect anything so now we're considering everyone who's the minimum guy the minimum guy is going to be 4 and then who is si connected to he's connected to a we already covered him and then F right now a tree where our tree is at is ca be e we have four nodes connected and we need to connect some more so what is the minimum edge that can expand this tree this connection of all of the nodes well it's going to be the AF edge so we'll take that one and now that F is a member of the tree we need to consider every edge coming off of the F and now well we never even knew about this edge one that value one edge if this were Chris Cole's algorithm we would immediately take that edge because out of all of the edges in the tree that's actually the smallest one and that's a different greedy strategy that we'll cover in other videos but for this one prim just discovered about this prim just figured out that this one edge exists this cost one edge because of the way we're building this tree iteratively so we're going to now take the fdh that's the smallest edge coming off of our minimum spanning tree and now that DS apart of the minimum spanning tree we can consider all edges coming off of him so now we consider the edge with six and along the way we need to we're using this visualization but in reality these edges that connect a node already in the minimum spanning tree to a node already in the minimum spanning tree those edges need to be not considered because we can't loop back into the tree that's a redundant edge so not not keeping up with that might have messed up the visualization a bit but ultimately at every step our goal is to do you see how all these notes have a focus on G G is the final node that is not in our minimum spanning tree because G's not in that we're focusing on all the edges coming to nodes not in the minimum spanning tree so before before we were had one node left we were only focusing on what nodes are not in this minimum spanning tree that I can reach from nodes in the minimum spanning tree pick the cheapest edge to get there we're gonna choose the cheapest edge to G which we could go through the D or the F we'll just choose the one in lower alphabetical order which is D and so now we don't want to connect back to the minimum spanning tree so we're gonna eliminate those edges from what can be considered and that leaves us with a minimum spanning tree where all of the nodes are connected all of the six nodes are connected by edges and this actually forms a tree and the reason we call this a minimum spanning tree is tree is just a special kind of graph and this is you normally see trees formatted like this so this is what the tree looks like so ultimately what is the cost of this minimum spanning tree the cost of this minimum spanning tree is going to be 21 this was the distinction we drew we walked through Dijkstra's we walk through prims and we saw the different greedy choices the greedy choice of Dijkstra is to minimize the distance from the start to any given vertex the greedy choice of prims is to minimize the edge that we add to the minimum spanning tree to expand the minimum spanning tree and not reconnect ourselves back to that same tree because we don't want to create a redundant edge we want to only create a connect to new nodes not in the tree let's minimize the cost to connect to them so that is the difference between Dijkstra and prints in other videos we could look at the time complexity but for this one this was just a conceptual grasp of both of these topics so if you haven't subscribed to the channel subscribe to the channel like this video if this was helpful and that's that's all for this one

Channel: Back To Back SWE

Views: 42,732

Rating: 4.9514923 out of 5

Keywords: prims algorithm, minimum spanning tree, dijkstra's algorithm, dijkstra, minimum spanning trees, computer science, back to back swe

Id: K_1urzWrzLs

Length: 20min 36sec (1236 seconds)

Published: Fri Oct 04 2019