3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy Method

Tapia's Dijkstra algorithm this algorithm is for single source shortest path problem if a weighted graph is given then we have to find our shortest path from some starting vertex to all of the vertices let us say I am selecting starting vertex s 1 then I have to find out shortest path to all the vertices may be a direct path or via other vertices and I can select any one of the vertices as a source vertex as we have to find out a shortest path so it's a minimization problem and the minimization problem is an optimization problem so optimization problems can be solved using 3d meth her greedy method says that a problem should be solved in stages by taking one step at a time and considering one input at a time to get an optimal solution and greedy method there are predefined procedures and we follow that procedure to get a optimal solution so Dijkstra algorithm gives a procedure for getting a optimal solution that is minimum result that is shortest path in this video I will show how our destroyed worth of its works and the disfavored custom can work on a directed as well as non directed graphs and also I will show you the drawback of Dijkstra Al Gore let us see the approach of Dijkstra algorithm for that I will show you the basic thing that is followed by Dijkstra so for that first of all I will take a very small example and show you - show the approach of Dijkstra algorithm I have taken a very small graph here from this we will understand what is the approach of Dijkstra if I see 1 is the starting vertex and I want to find the shortest path to 2 as well as 3 so if you see from this graph there is a direct path to what X 2 so its cost is 2 and there is no direct path to 3 so we don't know what is the path first of all we consider a directed path but now if we follow this rail Gotham will be selecting first the shot aspire to vortex so this is shortest because this is true that is infinity so we will select this one and distress is that once you have selected one of the shortest path then check yr that vertex from that vertex there is any shortest path to other vertices so let us check who is connected to to throw from do we can go 3 this is 2 plus 4 that is 6 and right now it is infinity yes this infinity can be change to 6 this means that there is a shortest path from vertex 1 2 3 of distance 6 no doubt it's not a direct path it's coming by r2 but there is a path that's how the Dijkstra algorithm always select a vertex with the shortest path then it will update the shortest path to other vertices if possible and this ablation is called as relaxation let me show you how this relaxation works for that I will call this vertex as u and this vertex as V and this is distance of U and this is a distance of V initially it was infinity now it is it change to 6 and this is cost of an edge from u to V so here relaxation means if the distance of vertex u plus cost of an ad G u comma V is less than distance of vertex means see here the distance of U was 2 and the cost of an edge was 4 and this was initially infinity so 2 plus 4 is less than infinity yes so we have modified this to 6 so will modify this one that is distance of V is modified to the distance of U plus cost of an edge u comma V that's what we followed and this is called as relaxation and we do relaxation for the vertices whenever we select a shortest path we will try to relax other vertices now let us follow this procedure and solve this graph problem to find out a spot let me solve this grass problem for this I will select this vertex as the source vertex starting vertex as starting vertex now I will give the distances for all the vertices by considering just single edge so I will label the distances above those what is this only this distance is zero and this distance is 2 this distance is 4 from 1 to 4 there is no direct edge infinity from 1 to 5 there is no delicate infinity similarly 6 is also infinity except 2 & 3 all are infinity this is the initial thing that we should do for any graph now let us start the repeating steps now the steps will be repeating first step select a shortest path out of 2 for infinity infinity infinity this is smallest select Aslam once we selected this we should perform the relaxation what is that check who are connected 3 & 4 are connected just check the distance of U that is 2 plus 1 P and this is 4 3 is less than 4 modify this then this is also connected to plus 7 7 is this is 9 and this is infinity modify this 9 that's all some vertices are relaxed they may or may not relax but we should check this one now second step now the step is repeating same thing I should do select the smallest one 3 infinity 9 infinity which one is the smallest she taught us this one select this one now check if any what X get relaxed so there is only one connected it's 3 plus 3 6 this is infinity so change it now select the shortest out of what 6 9 infinity which one is shortest this one select this one and see who are connected and try to relax them so 6 plus 2 is 8 and this 9 so this is more smaller modified 6 plus 5 is 11 this is infinity modified so 2 vertices are modified they are relaxed now who are remaining 4 & 6 who is minimum 8 select this one and check if anything gets relaxed 8 plus 1 is 9 it's all 11 modified so here I have taken an example most of the time the vertices are modifying their distances are modifying they may or may not modify now the last one is remaining is 6 so now we have the shortest path from starting vertex 1 to all of the vertices so what are the other vertices 2 3 4 5 & 6 what are the distances I got 4 2 it is 2 & 3 it is 3 & 4 it is 8 5 is 6 & 6 is 9 these are the distances of all the vertices and these are the set of vertices these are DVS and desire vertices so that's how a taster algorithm works on a graph to finding the shortest path let us little bit analyze and find out the time complexity of this algorithm if you analyze what it is doing it is finding shortest path to all the vertices how many vertices are there these are the vertices or we can also say n number of vertices so for all vertices is finding shortest path while doing so what it is doing it is relaxing relaxing which vortexes whether it is on 3 it is relaxed it has a lacks only 5 when it was on 2 it has relaxed only 3 & 4 so total how many what is this it will be relaxing we don't know any difference on the graph ok at the most how many words it may be relaxing all and is suppose to is connecting to all then it may be relaxing all of them it may be checking all of them so again it is V so it means n into n and for vertices and and what is those are relaxed so when it will happen that from - all are connected then again three all are connected that will be a complete graph in case of complete graphs it will take n into n time and this will be n square so this is the worst-case time of Dijkstra algorithm maximum time it may be order of n square I can write this theta of v square or theta of n square the worst case time and I can use theta there once I know that function that is n square and it belongs to some class that's n square class quadratic class so this is Theta of n square here I have a weighted directed graph commonly found in textbooks on this we will run Dijkstra algorithm to solve single source shortest path problem so I will not be updating the distances upon the word essence itself but I will be writing them in the table so let us see how I can prepare this table so instead of writing there I am writing here so initially I should find the directorate's pass through all the vertices so for two it is 553 it is fortified likewise all the paths are given and one thing to mention here the starting order is this one so in the graph you can see 1 to 250 1 2 3 45 1 2 4 10 1 2 5 no H 1 2 6 no H so 50 45 10 minute infinity already given let us solve it the smallest vertex is 4 so I'll select vertex 4 so the selected vertex is 4 then once the Hornets 4 is selected see from 4 5 is connected so can we relax this one so 4 is a 10 10 plus 15 20 5 yes 5 can be modified and we got a path that is infinity so it is 25 now and this remains infinity and the system which is already selected 45 and 50 there remains a letís now select the next smallest one so this one what x5 is selected so what x5 when s is selected there is an H 2 3 and there is an edge to 2 so if I take 2 how much is 525 now so I did not mention here 25 plus 20 45 and this distance is already 15 this is 50 but now we have a shorter path yr5 that is 45 so modify this 45 and this is also 45 this attend is selected 25 is selected this still remains infinity now I have to select the next shortest one so I have 45 45 infinity so I can pick up any one so I will select the second vertex to once word x2 is selected from there the connected vertices 3 so plus ten forty-five plus 10 55 but already the distance to 3 is 45 so 45 Plus 10 will be 55 so this is smaller no change so this remains as it is 45 is already selected this remains 45 only 10 is selected 25 is selected and infinity not elect next minimum so 3 3 is selected now from tree there is an edge coming towards 5 but 5 is already in the selected vertex don't shake it if you check also it's of no use see 30 is hung 3 is how much 45 45 plus 30 will be 75 so already 5 is having its weight as distance as 25 so no use of checking it so nothing is relaxed and this is selected that's all so 45 selected 46 is also selected then selected 25 selected infinity now who was remaining infinity is remaining so 6 is also selected so the part to vertexes has remained infinity only because there is no incoming edge on six so we cannot reach six the part to vertex six is infinity only that's how Dijkstra algorithm works this fell Gautam can work on non directed graph also suppose you have a graph simple example I will take here simple example I have taken here now how it works on this one so if you are not comfortable with non directed at chess you can convert them into directed by adding parallel edges so you can say this is 3 and this is also 3 now it becomes a directed graph so you can convert a non directed graph to directed graph right so it can work on both directed I realize no directed graph now I will show you the drawback of Dijkstra algorithm let us see the drawback of Dijkstra algorithm for that I have taken a very simple graph and it is having a negative weighted H the weight of this edge is negative so weight of an edge how it can be negative see it is not distance so distance is not not measured in passe negative right but any problem or any business problem we can represent it using cross well usually when we want to explain something to our friend then what we do we just take a paper and draw something so what is that it looks like the graph only so most of the problems from real world are mapped in the form of a graph so when you are representing something in the form of a graph it may have positive and negative grabs also so this is not exactly distance that is measured by tape but this is some value so those values can be negative also so actually the extra has not considered that if there are negative edges then what we should do he has not Sidda let us see what happens if you follow his procedures on this one let us start if I say this is the starting vertex then the distance is zero that the data gets passed is three and the data gets path is five and there is no directed spot so this is infinity this is the initial setup of Dijkstra now let us solve this one which one I should select the smallest one the shortest path is to select this one are there any connected vertices to this one so that I can relax no there is no outgoing edges from too late next select annex is smallest so 5 + infinity so 5 is smallest so select 4 if we select this for then will it relax any vertex yes the connected vertex is 3 so what is that part 5 + 2 7 so this is 7 now both are selected third one is remaining select that one also once this is selected shall we relax that one no no need all the D we learn that when all any vertex is falling relax Nouri to check it let us check it once 7 minus 3 is 4 nor it is 3 for that so all the things are perfect the answer is perfect so Dijkstra algorithm has worked even when there is a negative weight H now I'll make a small change I'll restart again I'll start over again and now I will make this edge as - check every what happens now I am again finding the shortest path to all the vertices this is the source vertex so it is 0 and this is 3 and this is 5 and there is no delicate spot infinity and performing this travels again because I have changed an edge now let us see select the minimum one so 2 is minimum selected anything gets modified no next minimum is this one anything get modified that's 5 plus 2 is 7 modify this next minimum is this one after the last one shall relax that no it's already selected but let us check it once 7 10 minus 3 now actually the part we found was 3 but now we realize that when we come along these vertices and reach here it is minus 3 so we were in a hurry to select the shortest path to vertex 2 when we select it as 3 it was wrong if we would have tried the other way we would have got the better answer so actual correct answer is minus 3 but Dijkstra has given us the wrong answer and also has us not to check those vertices which are Abed relax we should not check them because no need to check you will not find any better answer but here we are finding a better answer the reason is we have a negative edge so Dijkstra algorithm may work or may not work in case of negative edges that's all about single source shortest path problem and the approach was a greedy you can see you can see the greediness here see it is not trying all possibilities and selecting the minimum one it found that this minimum selected right just what the greedy approach so greedy approach has failed here when there are negative edges all right there is another solution for this single source shortest path problem that is Billman force algorithm we will see that in dynamic programming alright so next video will be on the dynamic programming these are the topics I have covered from parametric leave your comment so that I can know how you are following the videos right if any suggestion just give me I'll try to implement them in my next videos

Channel: Abdul Bari

Views: 1,649,846

Rating: 4.9214134 out of 5

Keywords: algorithms, algorithm, greedy method, single source shortest path, shortest path, dijkstra algorithm, dijkstra, abdul bari, bari, gate

Id: XB4MIexjvY0

Length: 18min 35sec (1115 seconds)

Published: Fri Feb 09 2018