4.2 All Pairs Shortest Path (Floyd-Warshall) - Dynamic Programming

the problem is all pair shortest paths in this video we will look at a problem and we will solve it using dynamic programming approach then I will show you what is the formula how we get the formula for dynamic programming and also I will show you a piece of code for solving a problem so let us start what the problem is the the problem is to find a shortest path between every pair of vertices let us say the starting vertex is 1 then I should find out our path from 1 to 2 1 2 3 and 1 2 4 then again selecting 2 as a starting vertex I should find a shortest path to vertex 1 & 3 & 4 similarly from 3 I should find a shortest path from 1 2 & 4 from 4 to 1 & 2 & 3 so this looks similar to single source shortest path that is Dijkstra algorithm but Dijkstra's algorithm will find out a shortest path from one of the source vertex and this vertex order of n square time if I run Dijkstra algorithm on all the vertices one by one that is all n vertices then I can get the result yes I can use the extra algorithm for solving this problem for all n vertices one by one and for each vertex it will take n square time and and the time will be order of n cube so this problem can be solved using reading method also but let us now see how we can apply dynamic programming for solving this problem now how the problem can be solved using dynamic programming dynamic programming says that the problem should be solved by taking sequence of decision in each stage we will take a decision so what decision I have to take let us see see if I have to find a shortest path between vertex 1 to 2 so there will be a direct edge path from 1 to 2 also like here you can see or maybe there is a shorter path going via vertex 3 or it may be going where a vertex 4 so in this way I have to check or decide whether a shorter part is going by or some other word so I'll start selecting the middle vertex as vertex one so I'll find out first whether there is a shorter path between all the pair of vertices going by a vertex 1 then Y a vertex 2 and so on so this is how we can take decision or sequence of decisions so how this can be done this can be done by just preparing mattis's explaining this a distance matrix see here from 1 to 1 or 2 2 to 4 4 to 4 there is no exit that's why all these are zeros means there is no X possible that loops are not possible then there is an edge going from 1 to 2 so 1 to 2 the cost of an edge is 3 and similarly there is an edge going from 2 to 3 so the cost of an edge is 2 so 3 2 2 3 the cost of an edge is 2 if there is no edge from 3 to 2 there is no edge you see so 3 - 2 is kept as infinity in case of absence of any edge we will take it as infinity otherwise for self loop we will show them as 0 now how we will solve this is we will solve it by preparing matrixes so let us see how madison's can be prepared let us prepare a matrix for 1 a 1 see this was a 0 original matrix now here I am going to consider the intermediate vertex has vertex 1 so is there any better shorter path going where vertex 1 so when I say vertex 1 then all the paths that belongs to vertex 1 will remain unchanged so I should not calculate them directly it can take them here so those values are 0 3 infinity and 7 and these are 8 5 & 2 so first row and first column already I have taken as it is then what about the diagonals there are no cells loops or and fill those diagonals also no remaining values I have to find out what are those first let us check this one that is 2 2 3 so how do you get this value how to check whether there is a shorter part of our vertex 1 or not so 2 2 3 I will take a 0 of 2 2 3 so what is there in this matrix 2 2 3 so 2 2 3 is a 2 and a zero of not in between I should include vertex 1 so 2 to 1 and 1 to 3 from those matters from that matrix 2 to 1 and 1 to 3 2 2 1 is how much 8 1 2 3 is infinity so this is 8 plus infinity this is infinity only this is less so there is no better path where vertex 1 so let it be to only now I have to find out next 1 that is 2 2 4 so a 0 of 2 to 4 what is the value there to 2 for 2 to 4 is infinity this is infinity now I should include vertex 1 in between as an intermediate vertex so a 0 of 2 to 1 plus a 0 of 1 to 4 so from that matrix find out 2 to 1 and 1 to 4 to 2 1 is how much 8 then 1 2 4 is 7 15 so this is 8 plus 7 this is 15 so this one is a smaller than infinity so update this part to 15 so this means that from 2 to 4 2 to 4 there is no direct edge path but 2 to 1 then 1 to 4 and that is 8 plus 7 15 there is a part going where vertex 1 that's what we got dancing here now I have to fill up these values right so that is 3 to 2 so I will find out a 0 of 3 2 in between I should add 1 3 1 1 2 so 3 to 2 is how much trying to 2 is infinity 3 1 5 plus 1 2 is a 3 so you can check there here infinite is greater so this value is smaller that is 8 so we got a smaller value 8 in the same way I should fill up all these values so I have prepared this matrix which is going via vertex 1 now I will prepare a matrix which is going by a vertex - so I should generate this matrix from this Mattox so what I am taking a second matrix - as a intermediate vertex then second row and second column remains as it is so I will take the second row second column as it is 8 0 2 and 15 second column is 3 0 8 8 3 0 8 8 and the diagonals remains 0 only now I have to find out few values here what are those first one is 1 2 3 let me find out from this matrix a 1 of 1 comma 3 a 1 of 1 comma 3 here 1 comma 3 is what infinity then in between I should include vertex 2 so a1 off in between 1 2 3 so 1 2 2 plus a 1 of 2 2 3 check this 1 1 to 2 is to 3 and 2 to 3 is 2 so this is 3 plus 2 that is 5 and this is smaller update this now this was infinity now we got a pathway our textu in between 1 & 3 1 2 3 there is a path going to 2 then 3 so 3 + 2 5 we got a path here so that's it now I should give this value 1 to 4 so a1 of 1 comma 4 is how much here 7 then in between I should introduce what x2 so 1 - 2 plus a 1 of 2 2 4 so 1 to 2 is how much 3 plus 2 to 4 is how much 15 so this 18 but this 7 which is already there which is better so take this 7 now in the same way I should fill up all these values already I have prepared this what extra as a intermediate vertex now I have to find out what X 3 has intermediate and generate the maddox when I say three as an intermediate vertex then the third row and third column remains a city so this is five eight zero one and this is five two zero seven and the diagonals are 0 a 2 of 1 comma 2 and in between I should take intermediate vertex as 3 then a 2 of 3 comma 2 so 1 2 2 is there so in between 3 is there and 3 1 2 3 and 3 2 - sort of this which one is smaller 1 2 2 1 2 2 is how much 3 there and 1 2 3 is how much 1 2 3 is 5 plus 3 2 2 3 2 2 is 8 5 plus 8 13 this 3 itself is smaller so take 3 only in the same way I can find out all these values by taking three years intermediate vertex now hope you have understood how I am getting the values so I will prepare all the mattresses so here are the four mattresses the finally the fourth vertex when I considered I got a shortest path between all pair of vertices so we have taken sequence of decision in each stage we were getting a matrix here the table is like a matrix here and finally these are the shortest paths between every pair of vertices what was the formula I was using I will prepare the formula getting the value of any matrix let us say 4 is the intermediate vertex or 2 is the intermediate vertex so when I was selecting one of the vertex of the intermediate vertex then how I was getting the values here I was getting from the previous matrix for 4 I was getting from three for three I got from two so how the formula can be framed so now I will show you the formula for getting a of I comma J of any intermediate vertex any value from any intermediate vertex I was taking minimum of a of I comma J from which matrix previous Mattox that is K minus 1 if I am generating care to than I was taking rally from K minus-1 either this or a of K minus one I to K what XK intermediate vertex SK plus a of K minus 1 then k 2 J so here you can see that case introduced in between and addition is done so either this one is a smaller or this one is smaller out of this whichever one is a smaller I was getting that one and I was following the same formula for generating all the mattresses I have shown only few terms that is sufficient for understanding the approach and how the formula is use see I have first shown you the working then I have generated the formula right and so following the formula I have deduced the formula that's it now let me show you how the code looks like if I am writing the code now let us look at the code every time I was generating the matrix so how many such mattis's I have generated for such mattresses I have generated right now for generating a matrix what I am supposed to do I should generate each and every term so total how many terms are there see the number of vertices are 4 so let us say n vertices so the number of elements are n cross n this is a square matrix now forgetting all the elements of a square matrix I should have to follow so I'll take two for loops for I assigns one I less than or equal to n I plus plus and for J assigned 1 J is less than equal to n J plus plus and I should get the terms of a of I comma J as minimum of a of I comma J that is existing matrix as it is going to be a single instance of 2d array in the single instance only I will be updating the values so that's why this is same thing then a of I 2k plus a of k2j out of this I should select any one of them whichever is minimum so what is K here K will be changing the intermediate mitosis so this whole thing will generate just one matrix and I have to generate all the mattis's so for K assign one K is less than equal to and k plus plus now first time K will be one so the intermediate vertex will be one all the time then K is a two so the intermediate vertex will be two all the time so K will take this value so when K is one the pneumatics is generated then k is a tude in the second Matrix is generated so this is for generating a matrix that's it this is the code for all pairs shortest path problem then if you look at this code this is having three nested for-loops so the time will be order of n cube so that's theta of n cube that's all about this problem

Channel: Abdul Bari

Views: 1,046,738

Rating: 4.9048786 out of 5

Keywords: algorithm, algorithms, all pairs shortest path, floyd warshalls, floyd-warshalls, dynamic programming, abdul bari, bari, gate

Id: oNI0rf2P9gE

Length: 14min 13sec (853 seconds)

Published: Fri Feb 16 2018