hey everyone welcome back to the channel I hope you guys are doing extremely well so in this video we are going to learn about the Bellman Ford algorithm now this is again an algorithm which will help you to find the shortest path yes I might be thinking but strive we already know an algorithm like diagram which helps us to find the shortest path how is this different it is the exact similar algorithm which will help you to find uh the shortest path from a source to all the other nodes yes to all the other notes but the only difference is if you remember the video of the diagram the dixtra algorithm fails when the graph has negative edges please remember if the graph has negative edges the dixtra algorithm will fail and there was another point if the graph has negative cycle the dixtra algorithm goes for a tle like it will keep on running it will keep on running keep on minimizing the distance it keeps on running forever so dijkstra does not helps you to detect negative cycle so Bellman Ford is an algorithm that helps you to detect remember this it helps you to detect negative Cycles as well that's a specialty about Bellman Ford and it is applicable and it is applicable only in DG what is DG directed graphs now you might be thinking what if it's an undirected graph then how do you apply Bellman Ford algorithm to it very simple remember this is how a directed Edge looks like so the edge weight will be five so there is an edge from one to two and the edge weight will cost you five but imagine if I give you an undirected graph and I say one to two and the edge weight is five so in order to implement Belvin Ford you need to convert this into something like one there is a directed Edge from one to two which will cost you five and there is a directed Edge from two to one which will cost you five so you just need to represent the undirected graph in form of a directed graph in order to implement the Bellman Ford algorithm the Bellman part algorithm will only work if you are given a directed graph remember this so if you are given an undirected graph just change it to a directed graph by having two side edges with the same Edge weights that is how you can always Implement Bellman Ford for any of the questions the only difference from dixtra is it helps you to detect negative Cycles what do you mean by negative Cycles imagine I draw your graph which goes from one to two two to three and three to one and the edge weight is minus two minus one and something like two so if I ask you the path weight what will be the pathway the pathway it will be very simple it will be minus 2 minus 1 plus 2 so minus 2 plus 2 will go and the path weight is basically minus one so if you apply diagram it will keep on rotating like sorry keep on encircling in the path because the path reduces at every stage so thereby dixtra will fall under the tle loop for such an example but when you talk about Bellman for Bellman Ford is an algorithm specifically designed such that it will tell you that Hey listen this particular graph has a negative cycle this is what you call as a negative cycle if a pathway is lesser than zero if a graph has any pathway which is lesser than 0 then I can say that the graph has a negative cycle now let's try to implement the Bellman Ford algorithm so I will be taking this particular DG which is the directed graph in order to implement development for algorithm and we know that it is a single Source shortest path algorithm so the starting point is 0 and these are the edges given to you so the edges will be given like u and v which means there is an edge from 3 to 2 with an edge weight of 6 there is an edge from 5 to 3 with an edge weight of 1 which is very obvious if you see this is this particular Edge and if you look at three to two this is nothing but this particular Edge so all the edges are given to you as something very very important to note down edges can be given in any particular order yes edges can be in any order like it's not necessary that you have to follow any particular order if you carefully see you can have three to six at the top you can have it here you can have it here you can have it at the bottom the edges can be jumbled it can follow any order what matters is you have to have all the edges of the directive graph the order can be anything very very important edges can be in any order now what does Melbourne Ford State the Bellman Ford will state you have to relax all the edges remember this relax all very very important relax all the edges n minus 1 times sequentially very very important point now what do you mean by relax y n minus 1 everything you will understand if you watch the video till the end so what they're seeing is relax all the edges n minus 1 times sequentially now what is the definition of relax let me write that as well well so the definition of relaxed States if you have a distance array and if the distance taken to reach you plus the edge weight that you require for an example you're standing at five and you want to go to three The Edge weight is one so this is The Edge weight that I'm talking about so if the distance of U plus WT is lesser than very very important is lesser than the distance of V which means as of now you add five they are trying to go to three with a one so whatever distance you took to reach this U which is five so basically distance of five plus this one if that is smaller than this whatever you took to reach 3 then you got a better guy similar to dijkstra so what you'll do is you will simply go ahead and say okay I got a better guy so I will be like distance V is equal to the new distance which is distance U plus W this is what I call as relaxation of edges this will be done for n minus one times what do you mean by n minus 1 times if you go over here and look at the n n over here is 6 because there are 0 1 2 3 4 5. like zero based indexing Edge uh notes so thereby n is six so you have to relax it for five times five iteration of relaxations has to be done now how to do it let's understand that but before that since you are calculating shortest path what do you require you require a distance array with everything initialized to Infinity so let's do that so initially when you initialize the distance array The Source will be marked as 0 and everything else will be marked as Infinity because you haven't reached anywhere so as of now you know you're starting from here and that is always going to be taking a distance of 0 but you haven't reached something like one two three four five so what you do is you just initialize them with infinity now how many iterations or how many relaxations you need to do n minus one what is n 6 so remember you have to do five relax session is what you need to do now in the first relaxation let me explain you if I say first relaxation what you need to do is now on the first I iteration what you will do is you'll go across the first Edge second Edge third Edge and so on to the last Edge you have to go across all the edges and that is when you say first iteration is done on the second iteration you have to go across again third iteration again both hydration again fifth iteration again you have to keep on going keep on going keep on going for five times okay so when I say first iteration what does that mean that's very very simple you have to perform this thing on every Edge one by one that is what you call as one complete iteration okay so the first iteration what will happen the relaxation of this Edge will happen then this so let's do the relaxation of the first Edge very simple I know I'm starting like distance of three I will take six in order to reach the distance of two because from three to two is where I need to go and I'll take a six so what is three if I look at three the value of 3 is nothing but Infinity so if I haven't reached if I haven't reached 3 is there a point in going ahead with three I haven't reached three so there's no point right so the relaxation of this Edge is done next you go to this Edge it's like from five to three oh let's again do the relaxation from five you take one and you reach 3 right so can I say 5 is still Infinity so you haven't reached you haven't reached five so if you haven't reached five there's no point next is this one which is zero to one so you like you can start from zero you will take 5 and you will reach 1 so when you say distance of 0 it says yes I I have reached myself it's a zero distance because I'm the source plus I'll take another five and I'll reach the one which was previously reached with infinity means not reached so I've got five so I can go and update this to five so on relaxation I update one of the notes to five perfect next is this guy which has to be relaxed which is distance of one minus 3 lesser than distance of 5 very very important distance of one minus 3 lesser than distance of 5 so if you carefully see we have a 1 here right do you see we have a one here so how much has one taken as of now one has taken a five so it's like five minus three lesser than distance of 5 which is infinity so 2 lesser than infinity so I can reach 5 in distance of two so go and update this with a distance of 2 and I can say the relaxation of this particular Edge has been done next is this guy so let's quickly relax this as well this is nothing but you can write distance of one minus 2 lesser than distance of 2 again what is distance of one if you carefully see it's nothing but five five minus 2 is 3 which is lesser than infinity so you get three so go and update this to three perfect done next you will go across and do this particular iteration so this is nothing but three so you can again write distance of 3 minus 2 again lesser than distance of 4 that's what you can easily write and can I say if you uh oh why is this coming up again and again wait so what I can say is what is distance of 3 can I see this that distance of 3 is still not Infinity so this will not be done next is the last Edge which has to be relaxed let's quickly relax the last Edge which is nothing but distance of 2 plus 3 lesser than distance of 4 what is distance of 2 let's see is 3 so 3 plus 3 is 6 what is 4 Infinity so can I say this will be updated to 6 so what I can say is the first iteration has been completed and on the first iteration we have got the updated distance values okay now you have to again do it which is the second iteration and the second iteration what you will do you'll again start yes you'll again start from the first now what is distance of three Infinity not reach what is distance of 5 this time you will find 5 has been reached with a distance of two why did you find because in the first iteration when you went Pi was updated somewhere here and now again when you come back and restart that five value which you updated here will be in use here so what is the files value to plus 1 which is 3 lesser than infinity so this will go as 3 go across and update 3 as 3 perfect next one this one what's the value of 0 0 so 0 plus 5 lesser than one that's still five not to be done what is one five five minus three is still 2 which is lesser than not lesser so not to be done again let's check out this what is 1 5 minus 2 which is 3 which is still not lesser what is distance of 3 this time this time distance of 3 has been computed what is distance of 3 this time 3 minus 2 which is 1 says 4 is it less than four yes because 4 is 6 so if four is if you see four is six what I'll do is I'll say distance of three was three minus 2 is 1 which is better than the current distance so I'll go and update this to one very simple because I started with three and I'll take a minus two distance in order to reach this guy again the last guy is this which is nothing but 3 plus 3 again 6 which is not better than this so I can say the second iteration is also done similarly you will do the third fourth and fifth basically again ramp again ramp again ramp and once you have done this this particular distance array will be storing all your shortest distance yes it will be storing all your shortest distance and if you carefully look at this it does not have a negative cycle it does have negative edges which is allowed but it does not have a negative cycle so ultimately after all the five iterations or n minus 1 iterations your distance array will be giving you the shortest path from The Source 0 to all other nodes remember this which will be stored in this distance array now a couple of questions y n minus 1 iterations that's the first question and the second question will be definitely how to detect negative Cycles so what if the graph has negative Cycles How will I know about that so because the entire algorithm is pretty much similar to dixtra because this portion is similar to dextra the only thing that we are doing is we are just doing n minus one iteration so obviously I want to know n minus 1 iteration because the thought processes n minus 1 is my question must be clear why because we just move ahead and this guy was updated this updated one then with the help of the one I got updated five then again when I came back with the help of 5A updated three then again when I went with the help of three I updated four and it went on moving So eventually everyone was getting updated updated updated updated on all the iterations so ultimately but how did I know that on N minus 1 iterations I will get my answer that's my question because what if I would have done two iterations what if you would have done three iteration the question still lies why exactly n minus one iteration has been done so let's understand that as of now so in order to understand the intuition or y n minus 1 because that is the critical question here because we have understood the thought process we knew one held me to compute because we knew 0 was the source which helped me to compute one one helped me to compute five and two and similarly to help me to compute 4 right and when I came back when I came back since I was I had computed five this five helped me to compute three and eventually this three helped me to compute four and so on it will just go on on this Loop thought process is clear but y n minus 1 is still the question let's understand this with this particular directed graph so in this directed graph if you remember while explaining I did tell you edges can be in any order edges can be in any particular order is what I always stated right so imagine I give you the edges in this particular order so how many notes are there the number of nodes are five so how many iterations will we have we will have one two three and four iterations because edges are five so I have to do n minus 1 which is 4 iterations correct so now what I'll do is I will start off with the distance array so let's quickly have the distance array so again to ease out understanding I have kept 0 as the source and made it a distance of zero okay now let's do the iterations so the first iteration States this is the first H so it states okay distance of 3 plus 1 Rd lesser than distance of 4 and it's like distance of 3 is still Infinity no go to the next one and says distance of 2 plus 1 are you lesser than 3 and I see distance of 2 is still Infinity no next one will be distance of 1 plus 1 is lesser than distance of 2 I'm like 1 is still Infinity no next I'll be like distance of 0 plus 1 is lesser than distance of 1. I'd be like wait 0 is 0 plus 1 is lesser than infinity so 1 goes as one so go and update 1 as 1. so in one iteration at the end of the day this one was updated so first iteration done okay now let's talk about the next Direction next iteration what is 3 Infinity next iteration what is to Infinity next iteration what is one so one plus one two so this will be updated to two so let's update it to two next 0 plus 1 not to be done so second iteration Dot so did you see what happened in the first iteration the zero got the value of 1. in the next iteration since you had the value of 1 since you had the value of 1 that one held you to get two so the third iteration what will happen come on what will happen think yes you are correct yes you are correct in the third iteration we don't have three but the second iteration gave me two when I go to relax the next Edge this too who has a value of 2 plus 1 will go ahead and update three so three will be updated to three perfect amazing so I see this is done next no more updates no more relaxation third iteration third iteration now what happened in the first zero updated one what happened in the second one updated two what happened in the third two updated three so what will happen in the fourth what will happen in the fourth yes yes yes the tree that you got will help you to update food so what did you get three it says three plus one four so this will go as four so ultimately on four iterations can I say ultimately on four iterations the distance array is ready and this is your shortest path yes this is your shortest path can I see this I can so thereby did you understand why n minus one because of the worst case you can have the guy at the bottom who will give you this then this will give you this and then this will give you this and then this will give you this that is why n minus 1 that is why n minus 1 yes I hope that's clear I find a lot of content over YouTube but no one will say you why and minus one they'll be like n minus one let's do it let's do it we got the answer quoted and that's done this is very important the thought process the intuition and the clarity about an algorithm is very very very important now the question is how to detect negative sign again thought process since I knew negative cycle means if I keep on because this will give you minus one again if I rotate it'll give you another minus one if I rotate another minus one on every rotation you are decreasing the path value by minus one so what will happen if there is a negative cycle so what will happen is if there was five iterations if there was five iterations if you do the sixth iteration the values will still reduce the values will still reduce on nth iteration the relaxation will be done and if the distance array gets updated because we have proved that at Max we will be requiring n minus 1 iterations we approved but even after that if I require on the other titration if I do a relaxation and even if I see distance gets reduced sorry distance gets reduced I will be right negative cycle exist because I know at n minus 1 iterations I should have gotten my answer but if at the end any titration if there is still a reduction it means we are running on the loop we're running on the loop that's why the distances are reducing are reducing so both the questions answered so it's now time to put it up so I hope you've understood the entire algorithm not sent to code it up so as usual I'll be coding the C plus plus on the right and you can figure out the exact similar Java Solution on the left so given a weighted directed and a connected graph of V vertices and E edges find the shortest distance of all the vertex from the source so they will be giving you a source if the graph contains a negative cycle then return an array consisting of only minus one and I think they've also stated if you cannot reach anyone you have to assign it with one E8 so what I will do is I have all the edges so I need the distance array so let's quickly you have the distance array of V comma 1 e 8 because I'm assuming I cannot reach them so that's what I'll give and now what I'll do is I will do the iteration or the relaxation for V minus one time because that is what I have clearly stated and I'm going to do the relaxation for V minus 1 times on all the edges remember this I'm going to do it on all the edges so this is 0 this will be V and the WT will be i t of 2. very very simple Okay now what's the next thing that I'll do I'll have to do the relaxation of edges so it's something like distance uh remember you have to give the distance of source as 0 otherwise you'll have an issue so remember distance of 0 should be reachable which means it should not be Infinity it should not be 1 8 and and distance of U plus WT lesser than distance of V if that's the case if it's reachable and if it's the case I see okay cool distance over you plus WT is what I'll do so this is how the Billman 4 will make sure the distance has the answer ideally you should have returned this but in the questions I've stated what code would have finished here but they have stated if it contains a negative cycle then return an array consisting of only one so you have to do one more relaxation this is the last or you can see the nth relaxation to check negative cycle is what you have to do return an array consisting of only one remember this so basically do one more relaxation which is nothing but this so you can say indu equal to uh ID of 0 you can say intv equal to ID of 1 you can again the same thing I T of 2 and you can go ahead and write the same if conditions of parallel copy paste I don't want to write it again and that's the case you have to return an array which consists of only one that's it and if that's not the case because you cannot reduce at the end of iteration all you should have computed all the shortest path in N minus one iterations at the worst case so what I'll do is I'll go and compile this and see if it is running fine it is now let's quickly submit this looks like all the test cases do pass so guys that is it about the Bellman Ford algorithm what about the time complexity V into e very simple V cross e is the time complexity the space is you're using an external V space and the edges is stored so pretty simple now this is this this is kind of a quadratic time whereas the dixtra was e log V so this is taking a bit more time than dixtra but it is very useful if your graph does has does have Negative Edge weights because dextra does not work so make sure if your graph has Negative Edge weights or if the graph has negative Cycles that's when you should implement the Bellman for algorithm do you get follow-up problems on this usually not in interviews they will generally ask you to tell about the building for or maybe they will ask you about dextra and at the end of the day they will ask what if the graph has negative edges or the Cycles what will you do so it might be a follow-up question on dixtra so very very important but I do not think the questions like you will find questions straightly related to Bellman Ford because most of the questions are solved using dijkstra's algorithm in shortest path so guys I hope you have understood everything so just in case you did please please please make sure you like this video and I was checking our statistics half of our audience does not subscribe to us they just watch our playlist and go so if you are watching this playlist please please please make sure you subscribe to us because that does matter to me a lot so please make sure you hit that subscribe button and yeah if you haven't checked out our DP series and the SD sheet the links will be in the description where this will be wrapping up this video Let's speed in some other videos [Music] don't ever forget your golden