4.4 Bellman Ford Algorithm - Single Source Shortest Path - Dynamic Programming

the topic is single source shortest path problem in this video I will show how build meant foot algorithm works and also the drawback of bellman-ford algorithm the problem is in a directed weighted graph we have to select one of the vertices as source vertex and find out the shortest path to all other vertices let us say if I select vertex one as one starting vertex so then I have to find out the shortest path to all of them before doing this already we have Dijkstra algorithm that will solve the shortest path problem but Dijkstra algorithm will not work if there are negative edges it will not work properly it may give correct result it may not give correct result so we cannot use the extra algorithm here and confirm that it is giving correct answer so we want a algorithm which confirms that the answers are correct so that algorithm is bellman-ford and it follows dynamic programming strategy so dynamic programming strategy says that you try out all possible solutions and pick up the best solution so here we want to try out all possible solutions and pick up the best solution how we will try all of them so this algorithm says that you go on relaxing all the edges how many times all that just you repeatedly relax them for n minus 1 time what is n here and it's the number of vertices number of vertices are 7 so I should relax them for 7 minus 1 what is the idea here if from the source vertex if the longest distance may be off all edges then total how many edges may be there so from 1 to 7 there can be maximum 6 edges so if you are going on relaxing that just we may get a longest path also that is of 6 XS right so it will cover all possible paths if you relax all of them for 6 times so what is relaxation if I take any two vertices let us say 2 & 5 and I know of some distance of this vertex in the path to this vertex and the path this vortex also then I should see that if the part of this one plus this is less than this one if so I will change this one so I will call them as you and me and I will write down just I will write down what does relaxation mean so then one I once I start using it I can explain you how it works so a relaxation means what between a pair of vertices u comma V if there is an edge then check if the distance of u plus cost of an edge u comma V is less than distance of V if so then change the distance of vertex V to distance of u plus cost of an edge u comma V what is that I will explain you while solving this now let us follow the algorithm what the algorithm says you prepare the list of all edges prepare a list so which as I should sell it first you select any edge first you select this one then this one or this one or this one you select anything but make sure that all edges are selected so I will select them vertex by vertex so I'll write on the list of edges here there are two Dalton edges I have taken all ten adjust here list of edges now have to relax all these edges for six times now let us start the procedure for initially I have to mark the distances of all these vertices so this vertex let it be zero and for all other vertices mark the distance as infinity market as infinity all are infinity now start relaxing the edges now I will show you how that relaxation procedure works first edge 1 comma 2 1 2 2 what is the distance of this one 0 what is the distance of this infinity 0 plus 6 is less than infinity 0 plus 6 is less than infinity so change this infinity to 0 plus 6 so make it a 6 the next 1 comma 3 0 and this is infinity so 0 plus 5 is less than infinity so change this to 5 0 plus 5 less than infinity so change it to 5 so first 3 it just completed now 2 comma 5 2 comma 5 this is 6 minus 1 this is infinity so this is 5 6 minus 1 is 5 this is already change you see 3 comma 2 so 3 to 2 so this is 5 minus 2 is the 3 so change it to 3 then 3 to 5 so this is 5 plus 1 is a 6 and it is 5 so that is smaller don't modify that 1 4 comma 3 5 minus 2 is 3 so this becomes 3 then 4 comma 6 5 minus 1 this is 4 this is infinity so change it to 4 then 5 comma 7 so 5 plus 3 is 8 this is infinity so change it to 8 6 comma 7 4 plus 3 is 7 this is less so change so most of the changes we have seen first time only let us continue second time 1 comma 2 so 0 + 6 6 + 3 so this is greater than that one so don't change that 1 1 comma 3 0 + 5 5 that is 3 don't change that 1 1 comma 4 0 + 5 this is 5 only no change then 2 2 5 - 2 5 so 3 - 1 2 this is 2 that is changing again so 3 2 2 so 3 is how much 3 3 minus 2 is 1 so this will change 1 then 4 comma three four comma 3 5 minus 2 this is 3 this is perfect for comma 6 5 minus 1 is 4 perfect 5 comma 7 5 is how much 2 + 2 + 3 - 5 this is 7 so change it to 5 then 6 comma 7 4 plus 3 is 7 and it is 5 no change let it be as it is I have completed 2 times 4 more times I have to do 1 comma 2 this will not change 1 comma 3 this will not change 1 comma 4 also will not change then 2 comma 5 1 minus 1 this becomes 0 this becomes 0 right then 20 comma 2 so 3 is how much 3 3 - 2 3 - 2 is 1 already 1 now no more changes the 3 - 5 so this is 3 plus 1 for all that it is 0 that is better for 2 3 4 - 3 is how much 5 minus 2 that is 3 no change 4 - 6 4 no change 5 to 7 5 is how much 0 0 + 3 3 this becomes 3 then 6 - 7 4 + 3 7 that tree is better right so I am updating there only so 3 times I have completed three more times I have to do what unto 2 will not change 1 2 3 will not change for the 4 will not change to 2 5 2 is how much 1 1 - 1 0 that is not changing then 3 - 2 so 3 2 - 3 is how much 3 - 2 one is holiday 1 then 3 to 5 so this 3 plus 1 4 that is better 0 4 to 3 will not change 4 to 6 will not change then 5 to 7 0 plus 3 3 only 6 to 7 no change now this has stopped changing so what are the results I got what x1 is 0 what x2 is 1 what X 3 is 3 what x4 distance is 5 what x5 distance is 0 what x6 distance is 4 what X 7 distance is 3 these are the distances I got if I continue for two more times also I will get the same result so finally these are the shortest paths you can observe that so as I am doing it manually I have stopped but when you write in any algorithm for doing the same thing it will continue for n minus 1 time and some graphs may get the shortest part in just one time relaxation only and some graph may relax completely get the shortest path in the last relaxation so in this graph we find that after the third one on words there are no change no more changes I have taken the shortest paths so this is how bellman-ford algorithm works let us get the time complexity of bellman-ford what it is doing relaxing all edges how many edges are they e edges are there how many times it is relaxing V minus 1 time so this is order of V into e so if we say V and E are n n so this will be n square so it depends on the number of edges if this is a complete graph then how many edges will be there in a complete graph a complete graph means there is AZ between every pair of vertical total how many edges will be there and into n minus 1 by 2 it just will be there so if these many edges are there then the time will be n into n minus 1 by 2 into number of vertices minus 1 n minus 1 so if you simplify this one this will be order of n cube so in case of create graph bellman-ford algorithm may take an Ncube time right otherwise minimum time we say it takes n square and at most it may take any cubed time that is if the graph is complete graph now we'll take a small example and solve it and also I will show you drawback of bellman-ford a small example I will take the list of it just first of all I will take the edges starting from here first I will take 3 comma 2 then I will take 4 comma 3 then 1 2 4 then 1 2 to see just to make you feel how the relaxation are done I have taken the vertices in the reverse I should have started from vertex 1 now let's solve this my source vertex is 0 and mark all of them as infinity mark all of them as infinity how many times I should relax there are 4 vertices so I should relax it for 4 minus 1 that is 3 times so let us relax all the edges at just one by one first three common to infinity minus 10 is infinity only so that is no change it is already infinity 4 comma 3 infinity plus 3 is infinity only and this is already infinity then 1 comma 4 1 comma 4 0 plus 5 5 is less than infinity so change it to 5 then 1 gamma 2 0 plus 4 4 is less than infinity change it before one time I already have relaxed second time 3 comma 2 infinity minus 10 s 4 that is better for comma 3 5 plus 3 is 8 this is better than infinity so you may get infinity 1 2 4 0 + 5 5 only 1 2 2 0 +44 only 2 times I have completed one more time I have to complete let us check 3 2 2 8 minus 10 is minus 2 minus 2 is smaller than 4 now you can see that I got the correct answer for vertex 2 now then 4 2 3 5 + 3 8 only 1 2 zero plus five five only one two two zero plus four and that is not great and not less than minus 2 so minus two is better let it be as it is so I have relaxed them for three times and I got the shortest paths so what are the shortest paths what X 1 is 0 what X 2 is minus 2 and vertex 3 is 8 what X 4 is 5 did these are the shortest paths for starting vertex s to so bellman-ford has got the answer even when there are negative edges so this is answer if I relax this for one more time and see let us what happens 3 comma 2 8 minus 10 minus 2 only for mine comma 3 5 plus the 8 only 1 2 4 & 1 2 2 all are same so if I relax one more time extra also there is no change that means the answers are perfect now let us see the drawback of bellman-ford I will take the same graph only but a small change the same graph I will add one more edge that is 2 2 4 and I will make it as 5 so this is 2 2 4 now let us relax them I have to relax them for three times so quickly I will do it because already till here I was doing it let us do so zero infinity infinity and infinity 3 2 to infinity only for 2 3 infinity only 1 2 4 0 plus 5 this is 5 1 2 2 as 0 plus 4 this is 4 now 2 2 4 4 + 5 9 this 5 is better no need of changing one time over now 3 2 to infinity minus 10 that is infinity so 4 is better for comma 3 5 plus 3 this is 8 then 1 2 4 is same thing only 1 2 2 is same thing only then 2 2 4 4 plus 5 is 9 and this is 5 that is better 2 times compared the third time 3 2 2 8 minus 10 minus 2 then so 2 3 5 plus 3 is 8 8 is there 1 2 4 s 5 only 1 2 to 0 plus 4 so minus 2 is better then 2 to 4 minus 2 and 5 is 3 this food is changing right so this was the third time I have done and I got this answer let me try for one more time already n minus 1 time I have done but let me try one more time and check 3 comma 2 8 - 10 s minus 2 only yes 4 comma 3 3 plus 3 6 oh this is changing 1 2 4 will remain same 1 2 2 also remain minus 2 only and 2 2 4 minus 2 2 5 is 3 only minus 2 plus 5 is 3 only so one more vertex has just now relaxed that should not happen after completing 4 n minus 1 time I should get down so if I repeat it for one more time if I relax all the edges there should not be any change at all if I do one more time again something will change see 3 comma 2 6 minus 10 minus 4 so that's what there is a problem so why we got this problem bellman-ford is unable to solve this one after performing for n minus 1 time also I am not getting the correct answer still they are getting relaxed so even if I do it without bellman-ford directly if I try to do I cannot solve it reason s there is a cycle of edges that is 2 & 4 & 3 so this is forming a cycle this is minus 10 & 3 & 5 so if I add this 5+3 8 minus 10 s minus 2 the total weight of a cyclist is negative so in this way I will be going on getting the path reduced every time so there is no end of this one so I cannot decide or freeze dance so if there is a negative weight a cycle then graph cannot be solved all right so bellman-ford fails to fight to solve the graph if there is a negative weight cycle total weight of a cycle is negative if it is positive it will work so if invade is negative it will not work that's all then but a bellman-ford algorithm can detect if there is a negative weight cycle or not because after performing for n minus 1 times we can relax one more time and check if the what is Azhar getting relaxed if any of the vertex is getting changed then it means there is a negative weight cycle so that's all about our dynamic programming bellman-ford algorithm

Channel: Abdul Bari

Views: 858,976

Keywords: algorithm, algorithms, bellman-ford, bellmanford, bellman ford, single source shortest path, single source path, dynamic programming, dp, abdul bari, bari, gate, bellman ford algorithm

Id: FtN3BYH2Zes

Length: 17min 12sec (1032 seconds)

Published: Fri Feb 16 2018