6.13 Dijkstra Algorithm- single source shortest path| With example | Greedy Method

hi guys welcome back today's topic is dice try algorithm so in this video I'm going to discuss with you the working principle of my algorithm and then what are the drawbacks of this algorithm okay so the extra algorithm is basically single source shortest path problem singles single source shortest path problem see the name suggests single source in this algorithm one source is given you're supposed to ask to find out the shortest path maybe and you are supposed to consider maybe with 0 as a source vertex and from 0 you are supposed to find out the shortest path to all the vertices or maybe you are supposed to you know ASCII 2 is the same two is the source and you're supposed to find out the shortest path from 2 to 1 2 2 4 2 2 a 2 2 5 2 2 6 you know like that to all other vertices so it is basically single source shortest path problem from one source you are supposed to find out shortest path to all other vertices ok now we'll discuss the working principle of this algorithm and after that I will show you the drawback of this algorithm okay see suppose this is a graph and you're supposed to find out the shortest path and source what X that is given to you is 0 0 as a source vertex maybe you can consider 5 as a source vertex and start your algorithm you can consider it as source vertex or maybe in question you are given 6 consider 6 as a source vertex then you are supposed to consider 6 as a source worst vertex and then you start the algorithm but here you'll consider 0 as a source vertex ok now first step is just you know mention the distance of this all these vertices from this vertex C we can we can easily say the distance of you know 0 to 0 the source vertex to source vertex 0 a source vertex that is why I am starting from this starting our algorithm from this vertex only so from zero to zero or distances zero and at first step the distance of all other vertices will be infinity infinity infinity like that we don't know what is the distance what is the shortest path okay now let us start we are going to start from zero from zero to how many vertices are directly connected to this this one and this four so we can find out the distance from 0 to 1 and 0 to 4 ok now how this distance is to be calculated like this suppose we are we are considering 0 to 1 we are calculating this distance so we'll consider 0s U and V sorry 1 as we so what is the formula see this is the formula distance of U plus cost of u to V and next we have distance of 3 C distance of U here we have 0 as you the distance of U is 0 plus cost of u to V V is the destination from 0 to 1 we are going to you know that find out the distance now here V is 1 the cost of edge u 2 V what is that cos 2 that is 4 okay and distance of V is starting May we don't know what is the distance of V that is because this is infinity so distance of these infinity the formula is if distance of U plus cost of u 2 V is less than D of V in that case what happens you see in this case 0 plus 4 is 4 & 4 is less than infinity okay so we will update this infinity to 4 we will change this infinity and will right here four because four is less than infinity fine and obviously we are calculating the shortest distance so if this is true then what happens the distance of V distance of V common a change curlier and distance of VK home a happening distance of U plus cost of you two this is the main formula to calculate the shortest distance okay now again find out from zero to four here this one is zero now sorry zero is you and now V is this 4 okay now from zero to four what is the distance distance of U is zero zero plus cost of this u - V edges eight zero plus eight is eight and it is less than infinity that is why we update it and we'll write here eight okay now this one takes is now selected a vertex or you can see visited vertex we have selected this zero now next is now take this vertex is already selected we have already find out the shortest path from 0 to 1 and 0 to 4 okay now this one is selected just leave it now check out the wall the remaining distance distance this one is 8 this one is 4 and every one every other distances infinity infinity and infinity now select the shortest distance shortest distance out of these is 4 okay now we will select this vertex this vertex is now selected okay now see this vertex is now selected from this vertex we can update this distance from 1 to 2 we can update from 1 to 4 and we can go from 1 to 0 will not update this distance Y say because 0 is already selected so once of what X is already visited or selected will not update the distance of that vertex ok so from 1 we will update this distance and this distance and when you will update if this bu plus cost is less than then only you will update now find out from 1 to 2 now in this case this is you and this one is we now find out this distance distance of you distance of U is 4/4 plus cost of you to the coast of u 2 vs 8 and distance always infinity and this one is less than infinity less than infinity in that case you'll update this distance so rather than this infinity will right here what this there's 4 plus 8 is 2 then ok like this we'll find out all other distances now from this to this find out distance of U is 4 4 plus 11 is 15 and this this distance of ways it okay but it is less than this 15 though we will not update this distance because if this plus is less than 2 you or DV then only we will update this but 11 plus 4 15 15 is greater than 8 then we will not update this one ok now this is already selected a 0 is already selected will leave this nodes now out of remaining nodes which node is having the shortest distance 8 infinity infinity infinity infinity 2l and infinity it is the shortest okay it is a less than or you can say the least distance you will select this for ok well select this this one now from this vertex we can update the distance of 4 2 5 4 2 8 4 2 1 4 2 0 but 4 2 0 and 1 will not update because 0 & 1 dot or are already selected or you can say visited ok so not update distance of these vertices elaborate four to five four to eight only now find out that this distance four to five distance now here this one is you and this one is the distance of you is eight plus cost of you to the u to V is 1 and this distance of ways infinity and this one is less than infinity 8 + 1 9 less than here then we will update and this one is 9 okay now find out this distance 8 plus this Coast is 7 7 plus 8 is 15 15 is less than infinity though we will update this distance okay this one is 15 okay now we have already updated now this one is selected this one and did this one of leave these nodes and out of these remaining nodes which node is having the shortest distance 9/15 to L infinity infinity infinity 9 is the shortest one then we will select this 9 now 5 is selected vertex from 5 we can update 5 to 6 5 to 8 distance okay we will not update 5 to 4 because this one is already selected ok now find out this distance 5 to 6 this one is now view and here now this one is we add this time ok 9 distance of U is 9 9 plus 2 11 11 is less than infinity we will update this ok find out this distance 9 9 Plus this coast is 6 9 plus 6 is 15 already 15 no need to change ok leave it any other we cannot update this one is already updated and only 6 and 5 are directly connected connected to the selected node so we have already updated this 11 and this 15 okay now just leave these selected nodes and out of this unvisited nodes which is having the shortest distance out of 11 15 to L infinity and infinity 11 is the shortest to select this one select 6 okay now from six we can update the name distance of those nodes which are directly connected that is three two will not update this one because this one is already selected okay we will not to visit this vertex again you can say it is already selected or visited from six to seven now this one is you and this one is we find out this distance distance of you is 11 plus 10 10 that is 21 21 is less than infinity we will update this okay this one is 21 11 plus 14 that is 25 25 is less than infinity we will update this that is 25 okay this one update this one also from check check out 11 plus this edges having distance 4 11 plus 4 is what 15 fine but here 2 is already having 12 and 15 is greater than 12 so we will not update this distance this will leave it as it is okay will not update this one any other you can update no ok now out of this at 4 unvisited node which is having the shortest distance 15 12 25 and 20 1 2 well as the short as 12 is the minimum distance will select this 2 n this node will be selected from this node you can update this distance and this one we cannot update this one because 6 is already updated and already visited we cannot update this distance because 1 is already visited find out from 2 to 8 now this one is this one will act as you and this one will act as V distance of U is 12 12 plus 2 is 14 and distance of V is 15 and 14 is less than 15 so we will update this one this one will become 14 ok now next is update this one also 12 distance of U is 12 this ghost of this u 2 V is 7 12 plus 7 is 19 and 19 is less than 25 so we will update this one this would become 19 okay now you'll not update this one will not update this one it's done now out of these three unvisited modes which is having short test distinct this one is having 14 this one is having 19 this one is having 21 then we will select this 14 because this is having the minimum distance vector we will select this 8 now from 8 you can up how many nodes are directly connected this 5 this for this - but will not update these this or this distance because 2 4 and 5 are already visited ok so we cannot update distance of any other node 3 or 7 car you cannot update from this hey leave it as a tease ok this one has selected now out of these two which one is having the shortest one you can show the minimum distance factor that is 19 and 20 or 19 then you will select this 3 3 you can update this distance only because these 2 are already selected then 19 plus 9 what is this 28 I guess 28 but 21 is less than 28 so we will not update this one ok now only one node is there you will select 7 only and this one is 21 only because we will not update these distances ok so using this formula this is the working principle of destra algorithm ok see if I ask you what is the shortest distance from 0 to 3 then the answer would be this 19 what is the shortest distance from 0 to 8 then the answer would be 14 what is the shortest distance from 0 to 6 that is 11 shortest distance from 0 to 7 that is 21 from 0 to 5 9 from 0 to 4 we have 8 from 0 to 1 we have 4 from 0 to 2 we have shortest distance is this 12 so this is the working principle of Christ algorithm now see this diester algorithm works on undirected graph and directed graph as well okay now we'll take one more example of directed graph okay now let us say we have this graph which one is directed and related to the RAF and we're supposed to find out the shortest path from the source vertex and source vertex is a to all other vertices okay let us suppose a source vertex may be in question you are given that consider see as the source vertex okay now in the previous case we have already updated the distance in this graph only but in this case I will draw on table and we will update the distance in that table only okay see now we will draw a table is B C D and these five vertices we have starting may you're right that vertex which is the source vertex suppose in question you are given consider B as a source vertex okay in that case you would have written here B and here you can write a C D and E like that only in any order but the source what X must be written in at first only okay here we have consider source vertex is hey hi okay now the very first step is just the same thing we have already done in previous example that is 0 to 0 distances so the a to a distance would be 0 and back the other remaining distances would be infinity so the distance of this this one is 0 this one is infinity infinity infinity is infinity this is the first step the stance of source to source would be 0 ok now out of these which one is having the minimum distance vector that is 0 okay so we'll select this will select this 0 and the vertex is a okay now from a - how many vertices you can find out the distance ay to B and a - see see there is no that edge from A to E there this edges from E to E so we cannot update from A to E we can update only a to see and a to B now find out the distance from A to B distance of a is zero same formula distance of U plus cost of u to V and distance of B if this one is true then we will update distance of V to distance of U plus Coast ou2 we use this formula okay now find out from A to B distance of a is 0 0 Plus this coast is 10 okay and 10 is distance of B is what infinity 10 is obviously less than infinity we will update here 10 only what about C A to C 0 plus 5 is less than infinity we will update here 5 only D will not update to e will not update because there is no direct edge from A to D and a - yeah okay this one is done this one is already selected we will not write this in another in the next row now out of these four which one is having the minimum distance factor that is 5 10 or infinity or infinity that is 5 then we will select this Phi ok that is see see what X has been selected now from C they can update distance of C to B C - B and C to e ok now find out the distance C - B what is the distance distance of C is what this 5 ok see if we have selected this 5 so we will consider this distance distance of C is now five you can say distance of you is five five plus distance of C to B what is this cost of this edges three five plus three that is it and distance of this this one is distance of V now here V is the distance of B is what ten and this 8 is less than 10 previously say it was 10 previous okay but we have selected C and through C if we go to B A to C then B then what is the distance distance of C C is 5 5 plus 3 is 8 so 8 is less than this 10 that will update this can write it okay now next from C to D distance of C is 5 this coast of this edge is 5 plus 9 that is 14 and previous it was infinity and 14 is obviously less than infinity I will update this from C to e what is the distance distance of C is 5 5 plus 2 is 7 so we will update this ok we will not write this 5 again because we have already selected this 5 ok now out of these three which one is minimum that is say when we will select this vertex that is easy it would be selected now from E we can update the distance of being distance of a but will not update this distance Y so because a is already selected these are selected vertex or you can say visit you to vertex so you can say mark vertices ok now e to a will not update we can update only e to D because we have edge from e to D now find out the distance e to the distance of E is 7 okay 7 plus this coast is 6 7 plus 6 is 30 and the stance of D is 14 previously and 13 is less than this 14th we will update here 13 now can you update this distance he we have selected this e can you update a to be e to be no there is no edge then you'll write as it is here 8 okay now we have only two vertices which are unvisited out of these two which one is having minimum distance factor that is 8 will select this 8 and the vertex s B B would be selected then from B we can update only this B to B ok and all we have only one vertex that is remaining now find out this distance B to D what is the updated distance distance of B is 8 8 plus this host host is 1 8 plus 1 that is 9 okay and previously the distance of B is 13 and 9 is less than 13 then we will update here 9 ok will not write this one here and now we have only one vertex that is unbusy good then obviously we'll select this vertex this vertex is d this is the table through which you can find out the minimum distance now if you are asked what is the distance shortest distance from A to D A to D so what is the shortest distance that is 9 from A to E 7 from A to C 5 from A to B 8 ok now second thing is if you want to find out the path suppose we are supposed to find out the shortest distance from A to D plus the path ok maybe there would not be the direct edge from A to B we have how many a to pail ahem they may be B C then D so you how to find out that part okay now what is the form know that how to find out that that path suppose a 2d we are supposed to find out okay a 2d in shortest distances 9 we have selected the vertex B here only okay now one pointer would be set at 9 only okay and here I'll write the path here I'll write the path only okay this 9 okay the selected vertex is B we are supposed to find out the path from A to D only okay this 9 is the shortest distance in the path is B we have selected be here only C D okay then suppose in path I'm writing B now we'll move this pointer one step backward how many hop and then I'll go to one step backward I'll go here only okay and this has been changed see palette is at this point it was 13 and after that it has changed to tends to 19 so in this case either you change fobia here so we'll check in this row which what Isis has been selected which vertices has been selected this one and this one is what B B has been selected okay pointer will be here only now I write here suppose B B has been selected then we'll go one step backward here eight only okay no problem typically when you say Mikey you will move one step backward Jessica value changeover okay at that point you have to do something now one step backward here only it is 10 but the next step it was it so this has been changed here only okay now in this row they have a value change we this row which what is what is what ex-husbands electric that does this one 5c she has been selected then ill right here see pointer would be here only now go one step backward okay your habit high infinity habit change okay take care the same step change what you care though you will check in this row which vertices has been selected this one zero this Kristin see and that is hey that is hey we have a race to the source vertex that is zero so the path from A to B is a C then B then D shortest path and the distance of this path is what does this nine you can check out in this you can check out this path through this graph only see a to see what is the distance a to see Phi Phi C to be C to be that is three plus then B to be B to D one and this one is five plus three plus one is nine and already we have find out the shortest path that is shortest distance that is nine same suppose the shuttle you have to find out shortest path and shortest distance from A to E from A to B suppose okay what is the path and what is the distance a to be the shortest distance is you simply just check this table and you can totally say that the shortest distance is 8 a to be and find out in this Colin what is that selected that number is 8 so 8 is the shortest path should you sorry the shortest distance but what is the path ok now how to find out the path same formula just give a pointer here 8 because we are supposed to find out the shortest path from A to B B this one is 8 rules just set up a pointer here move this pointer one step backward this one is 8 only no need to do something because 8 & 8 both are same go to one step backward here it has been changed N & 8 so Joe happy a change we in that row only find out which what is which vertex has been selected this vertex that is C C has been selected okay the path has B then in this one C has been selected you will write C okay this one C has been selected then pointer would be here only then one step backward here it was infinity change watch okay infinity to 5 the change who I throw in that row which vertex has been selected this one and this vertex was he and we have already reached the source vertex that is 0 the path has a C and B and the distance is 8 a C and B you can find out 5 plus 3 is 8 so this is the table you can find out using that table the path as well as the shortest distance now the drawback of this destra algorithm is what it will not work you see I am NOT saying that it will not work it may or may not work when the edge beta- also you show you with the help of one example okay okay now let us take this graph which one is having negative edge weight that is minus strength now suppose find out the shortest distance one is the source vertex so 1 2 1 0 and remaining would be infinity and infinity you know find out 1 2 p 0 plus 5 that is v zero plus 10 that is in okay now one has been selected now out of 2 3 & 4 which is having the less distance vector that is out of 10 infinity and 5 which one is less less 2 that is 5 you will select this vertex - okay now from - can you update any well but X this one this one this one no we cannot update because there is no direct edge okay this one is selected out of these two now we will select this 10 because 10 is less than infinity now from 3 to 4 we can update 10 plus 1 that is 11 okay 10 plus 1 that is 11 now we have only this vertex will select this for now we can update can you update this distance for 2 to know according to the principle of tester algorithm you will not update this one because 2 has already been selected to has already been visited okay but suppose you are updating this distance a graph update coming here then what would be here see from distance of this this one is you this one is V distance of you is 1111 - n that is 1 okay if we go from 1 2 3 to 4 to 2 then that distance would be 1 and 1 is less than 5 fine but we cannot update here only why so because 2 has already been visited and according to drive Strela rhythm a node which has already been visited we cannot update the distance of that vertex so the Esther algorithm in this case is having the wrong shortest distance because according to the Australia rhythm the shortest distance from 1 to 2 is 5 but that is not actually true the shortest distance from 1 to 2 is 1 through 1 2 3 2 4 2 2 so that is the main problem of diaster algorithm see it that is not always true sometimes may be you know suppose that if suppose this one is minus 1 let us suppose I am changing this this one is minus 1 now now the distance is 11 minus 1 that is n and 5 is less than 10 so this one is right okay so does try algorithm a drawback is it may or may not work when it have negative edge weights okay but it will surely not work when it will have a cycle which is having negative weight okay negative edge hoagie only in that case it may or may not give the correct result here characterized LD be supply and maybe this a tie but in case graph make s a cycle here which is having negative weight total edge weight of that cycle is negative then surely it will give you incorrect result okay so okay I'll see in the next video till then bye-bye take it you

Channel: Jenny's lectures CS/IT NET&JRF

Views: 481,003

Keywords: dijkstra's algorithm, shortest path, data structures and algorithms, sorting algorithms, bellman ford algorithm, greedy algorithm, algorithm complexity, shortest route, all pair shortest path, brute force algorithm, algorithm in data structure, dijkstra, quicksort, ugc net computer science, GATE computer science preparation, data structure, notes, engineering, single source shortest path, algorithms, technical channel, best youtube channel, greedy method, NTA ugc net 2019 syllabus

Id: smHnz2RHJBY

Length: 34min 35sec (2075 seconds)

Published: Tue Feb 12 2019