6.15 Floyd Warshall Algorithm All Pair Shortest Path algorithm | data structures and algorithms

hi guys welcome back today's topic is all pair shortest path problem the first of all with the help of this example we will understand what is this problem let us suppose this is a graph weighted graph okay and then for this graph we are supposed to find out this all pairs shortest path ok now what is this problem suppose you are taking this vertex 1 ok as a source vertex then you are you will find out the shortest distance to each vertex like suppose 1 2 2 1 2 3 and 1 2 4 fine now if you take 2 as a source vertex then 2 2 1 2 2 3 2 2 for shortest distance find out cornea from 2 to 1 2 to 3 & 2 to 4 if you take 3 as the source vertex the state 3 to 1 3 to 2 and 3 to 4 and if you take 4 then 4 to 1 4 to 2 & 4 to 3 this is all pair shortest path problem ok first it a two at one time you will select any one node and you will find out the shortest distance from that node that node to each other node take it like this 1 say 2 3 4 then to say 1 3 4 and like that this is all pair shortest path problem see what is there in the Astra algorithm in that case that algorithm is basically a single source shortest path okay in that case single source would be given and that algorithm can find out the shortest distance from that single source to all other vertices like this if you apply the extra algorithm in this case then how many times you have to apply 1 2 3 & 4 times 4 times tester algorithm can be have to applied in this case to find out the all pair shortest path t-take a because that is single source a time pay one source that algorithm will select taken from that source it can find out the shortest distance to each vertex ok but it's like in one execution only you can find out the distance between the shortest distance between between every pair of this every pair of the vertices of this graph fine so rather than applying four times diaster algorithm one another solution is there that is this floyd-warshall algorithm fine now this algorithm is basically you know based on that it follows the dynamic programming approach what is dynamic programming approach that is basically no simplifying a complicated problem by breaking it down into simple sub problems in recursive manner fine or you can say endemic programming some sequence of decision is to be taken out at each step and finally you will get the result of that problem okay second advantage of this fluid warshall algorithm is what this algorithm also works on a weighted graph having both positive and negative edge weights fine but - - algorithm only works on the graph having only positive weights on the edges fine as you see in this graph we are having some positive weights this five one two six and this one is - or this one is negative okay so if you apply diester algorithm in such kind of graph then that algorithm would give you some wrong result fine if a graph is having negative weights then this algorithm would be used or bellman-ford algorithm also can be applied on the graph having negative edge weights right the first of all we'll see the working principle of this algorithm then we will draw the formula of this algo okay now see suppose from one to two we are supposed to find out the shortest distance here is one directed that is having edge weight nine but it is also possible that we can go wire three to two and we can go via the vertex four to two and maybe these roots are having short shorter distance than this direct path it may be possible when you go from one to three and then two then this path would give you maybe shortest path rather than this direct end this one fine so simply we will first of all will take this this one as a middle vertex and then we'll find out the shortest distance between each pair of vertex then we will - as a middle element then we'll three as a middle element then we'll four as a middle element and find out the shortest distance between each pair of vertices fine okay now see first of all first step is draw a distance matrix fine see only the single execution of this algorithm can give you the result can give you the shortest distance between each pair of vertices fine in only a single execution of this algorithm fine okay now see try to make a distance matrix first of all and we'll denote it with d0 I hope everybody know how the distances to be prepared see if you are having four vertices then the matrix would be 4 into 4 if you are having 6 vertices then the matrix would be 6 into 6 fine now all the diagonals would be 0 because 1 2 1 we don't have any edge fine so 1 2 1 0 2 2 2 0 3 2 4 2 4 0 this is the rule all the diagonal elements would be 0 the distance from 1 to 1 would be obviously 0 fine now the distance from 1 to 2 fill out the stable distance from 1 to 2 see in the graph 1 to 2 distances 9 C this one is directed graph talk to the hand of my - - that is 9 2 2 1 is 6 2 2 1 is 6 1 2 3 1 2 3 - 4 1 - 4 is there any edge directed from 1 to 4 no then the distance will be infinity if you don't have any direct edge between two pair of vertices starting mouseka distance how there will be infinity now from 2 to 3 2 to 3 distance is 2 to 3 is there any directives no this this one is 3 to 2 not 2 to 3 that would be infinity fine next is 2 to 4 yeah that is 2 3 to 1 is 3 to 1 is no we don't have so that is infinity because it is 1 2 3 3 2 2 3 2 2 yes we have we have an edge 3 to 2 and having that wait 5 3 2 3 apna has zero 3 to 4 3 to 4 no we don't have any edge that would be infinity fine now 4 to 1 4 to 1 is infinity 4 to 2 is infinity 4 to 3 is 1 fine this is our distance matrix initial distance matrix fine now we would take we would consider 1 as a middle vertex and then we'll find out the distance of the shortest path between each pair of vertices via one cya 1 fine now D 1 you are supposed to calculate distance matrix and when you are going to calculate this T 1 this D 0 would be your base matrix you can see you will consider this one and from this matrix you'd draw D 1 fine the d1 would be like this you can find out D 1 1 2 3 and 4 1 2 3 & 4 this would be the matrix fine now see if you are finding this be one means one is that middle element will go via one fine d1 to the this row or this column and this row corresponding to this one would be acting as working : or working row fine working column and working no okay now this were this call this column and this row would be you would write these values as it is in this vertex because if you are considering one as a middle vertex then is K corresponding tobio vivo values of ki kahani as a T's old print in this matrix then the values are zero six infinity infinity nine minus four and infinity fine next step is all the diagonals would be zero these are two steps now third is the main step you are supposed to fill out these entries also now how you will find out this distance fine okay now the formula is now we are supposed to find out distance from this this one two to three point two to three distance should be one up go find out Kearney hat D 1 2 2 3 ok now C D 0 2 2 3 check out the direct distance belly-up Chikurubi starting my distance calathea 3 2 2 3 what was the distance that is infinity and if you will go why are this vertex 1 then what would be the distance now you how you will write this D 0 see I put Jana had 2 to 3 but wire this one so first of all you would go from 2 to 1 plus D 0 1 2 3 this is the middle element or you can say that that element that why I element okay find out from 2 to 1 2 to 1 what is the distance 6 + from 1 2 3 1 2 3 what is the distance - 4 and the answer is 2 fine and obviously 2 is less than infinity fine so you take the minimum distance either this one or this one this one is minimum so we'll take this distance - and you'll write 2 here not that infinity because how many calculate here that is less distance and obviously we are finding the shortest path okay so it means when you go from 2 to 3 wire 1 then it would take the two coasts coasters to take it or paheli opteka the infinitely - abisco update card OE because a minimum is now C 2 to 4 calculate guru D is 0 2 to 4 what was the distance first of all upper you take near to 2 for the distance was to initially and if you are supposed to calculate this distance why are this one means d0 first of all 2 to 1 plus D 0 then 1 to 4 fine now check out this distance to 2 1 to 2 1 that is 6 plus 1 to 4 1 to 4 that is infinity and obviously this would be proximity and 2 is less than infinity there will not update this distance will keep this as a teach to minimum output euskara is missing fine Ecore calculate curtayne see suppose 3 2 to be 0 3 to 2 what was the distance 3 2 to 5 see up is to calculate career matrix code roca río 2 is co-op consider the Roubaix your hockey values they came up is called recursive to take a 3 to 2 aku cannot open a up value there Co 3 to 2 what was the value initially 5 and if you will go 3 2 - why a 1 then what would be the distance D 0 3 2 1 Plus D 0 1 2 2 fine now find out three two one three two one that is infinity plus one to two that is nine it is a aprox infinity and five is less than infinity they will keep five has a tease you will not obtain this infinity here fine like using this formula you are supposed to fill out this this and this also okay now this is a beaver fine we have already find out the shortest distance between each pair of vertices via vertex one wire one now we'll find out why our takes two that is D - fine and when you are preparing this D 2 matrix you will consider that D 1 as base matrix a peony dikko gap you'll calculate the values of this matrix using these values D 1 values meth lab - hello - 1 if this one is K 2 K minus 1 coop consider Carabas codec a you will find out the value of this matrix okay same step all the diagonal elements first of all would be 0 second step was what if you are considering - as a metal element then the corresponding row of this 2 and corresponding column of this 2 would be as it is here fine so right now this one is 9 this one is 5 this one is infinity this one is 6 this one is 2 this is 2 fine now find out the remaining values using the same formula the formula was see how me find out Kani the value of 1 2 3 D 2 1 2 3 you will consider this matrix D 1 fine to check corrode B 1 1 2 3 what was the value 1 2 3 - 4 fine now if you want to go from 1 2 3 wire - then what would be the distance D 1 first of all from 1 to 2 then we would go from 2 to 3 C Y ax - we are going from 1 to 3 direct opti a Thea ba calculate Karnas OD 1 1 to 2 D 1 1 to 2 is 9 plus D 1 2 2 3 2 2 3 is this - and the distances 11 of Bruce Lee - 4 is less than 11 so we will write here - for only the same one because this one is related and you are supposed to take the minimum from the out of these - fine now a core calculate 13 this d12 for a calculator d112 for check out what was the value infinity now check out from 1 to 2 via this to d1 1 to 2 plus D 1 to 2 for fine finally you are going from 1 to 4 but via this element wire this to find out the distance TD 1 1 2 2 1 2 2 is 9 + 2 2 4 2 2 4 s 2 and this one is 11 11 is less than infinity tool right here what 11 you will obtain this value fine like this only you will fill out all the values suppose we calculate Kirti hey this 3 2 1 now check out D 1 3 2 1 D 1 3 2 1 was infinity now find out the value from 3 to 1 but why at 2 so first of all go from 3 to 2 then D 1 to 2 1 fine what is this value D 1 3 2 2 3 2 2 is 5 + 2 2 1 2 2 1 is 6 that is 11 11 is less than infinity you will write here 11 only rather than this infinity because 11 is minimum out of these ok like using this formula you will fill out these values also okay okay now this is d2 matrix fine now you will take three as a middle element and you will find out the minimum the shortest path between each pair via this three okay now I will create this B 3 matrix and for creating this d3 matrix we will take d2 as base matrix we will use these values and then we will calculate D 3 values of T 3 the first step is what all the diagonals would be 0 next step is what C 3 is we are taking 3 as middle element to the corresponding row and column of this 3 vertex would be as at ease here - two - here is one here is 11 and here is 5 and 7 right now find out these values using the same formula what is the formula what you have to find out you are supposed to find out 1 to 2 is Co filter o 1 2 to take a values of K consider karaage check her over yaha faith one two to take a check out D - 1 - 2 what is the value sorry 1 - 2 that is 9 and if you would go 1 2 2 via this 3 then what will be the distance means D - first of all we will go from 1 2 3 plus then we would go from 3 to 2 fine find out 1 2 3 - 4 + 3 - 2 5 an answer is 1 and 1 is less than this 9 okay so we would update this value we would write here 1 rather than this night take it no one is minimum find out this one also one two four one two four s11 now we would go wire three three to four would go wire three so 1 2 3 1 2 3 - 4 + 3 - 4 is 7 value is 3 + 3 is less than this 11 so it would update this value 3 will not write 11 will write 3 ok using this formula you will fill out this table fine so this is B 3 matrix now we would consider for as a middle vertex and you will find out shortest distance between each pair using this formula only you will calculate this or you can say you'll prepare this D 4 matrix fine the same rule the diagonals would be 0 0 and 0 if metal element is 4 then this row and this column would be considered as working row and working column corresponding to this vertex for fine you will write down these values and as a T's 12 6 one this one is 3 2 and say fine and you are supposed to fill out these positions also fine using that formula only let us find out from 1 to 2 you find out guru d 4 calculate car ahem so you will consider D 3 as a base matrix or you'll use this one and from this one you you are going to draw this D 4 matrix so check out 1 2 2 D 3 1 2 2 D 3 1 2 2 was 1 now you could go from 1 to 2 y overtakes this 4 then D 3 first of all go from 1 to 4 plus D 3 then 4 to 2 1 to 4 what is the value 3 that's 4 2 to 4 to 2 what is the value 6 9 + 9 is 1 is less than this 9 so we would keep this value only you'd write here 1 only you not update this value because 1 is like minimum from this one and 9 to keep this value only right now find out from 1 2 3 D 3 1 2 3 find out check out 1 2 3 that is minus 4 now if you will go from 1 2 3 wire this 4 because 4 is now made middle vertex 1 2 4 + D 3 4 2 3 this is what the value D 3 1 2 4 1 2 4 is 3 + D 3 4 2 3 that is one fine 1 2 4 is 3 & 4 to trace this one and minus 4 is less than this one they will give this value will be minus 4 on using this formula you will find out all these values so this one is our D 4 matrix so we don't have any other vertex finally I am demmas for vertex NATO for distance matrix would be there one is that initial one fine so this matrix would give you the solution this matrix would give you the shortest path between each pair of vertices you can choose any vertex suppose you are choosing this 3 as a source vertex the 3 3 2 1 3 2 2 & 3 - 4 what is the minimum what is the shortest path 3 2 1 you just check out this final vertex 3 2 1 3 2 1 11 would be the shortest path 3 2 2 3 2 2 5 would be the shortest path and 3 - 4 is 7 would be the shortest path like this if you are searching to this 4 as a starting vertex 2 4 to 1 to n 4 2 to 6 and 4 to 3 would be 1 the shortest path fine ok now you would draw the formula I am going to run this now will see the formula take a working principle say will draw the formula see this one is the formula to generate this matrix to find out the shortest distance C we will see this formula you are supposed to find out the distance DK from I to J I and J as for row and column okay DK I - for suppose we are taking K value is 4 let us take K is 4 and here we have taken I value is 1 and J value is 2 fine you are finding this 1 - 2 is 1 J is 2 and K value is this for this value you are finding the what was the formula cb4 go calculate karna had to Chanukkah consider katha we have taken B 3 that is K minus 1 take a K minus 1 IJ take a minimum of these two the minimum of D K minus 1 D 3 IJ or minimum or this one D 3 d 3 MATLAB K minus 1 because K is for fine here 3 2 K minus 1 K minus 1 I 2 K I is a 1 and you happy ki happening a key value for K is equal to 4 2 here what is the formula I 2 k plus plus DK minus 1 k 2j k 2j j key value whom i pass Kathy - and you are taking the minimum out of these to see how many dono calculate Yatta Yatta Yatta Yatta 1 to 2 is 1 then D 3 1 2 4 4 2 2 3 plus 6 that is 9 we have taken these values from this what XK is for I is 1 and J is 2 we are just taking an example suppose we are finding the value of this 1 K 1 2 for this one fine and K value is 4 K is 4 okay I 1 J 2 now we have for finding this value we have considered d3 much up the value of d3 MATLAB K minus 1 K minus 1 minimum of DK minus 1 IJ c b1 poop to find out carney omni 2d 3 1 2 2 a sub D K minus 1 I 2 J and minimum of these two - minimum of day 3 D K minus 1 miss because K is for I 2 k plus K 2 J this formula because K is 4 and we have taken minimum of these 2 so this is the formula to generate this matrix fine this matrix for this K and K is this one food so care when cave and he would be this one then D 1 matrix would be generated using this formula and K value would be 2 then D 2 matrix when K value would be 3 then this matrix when K value would be 4 then this matrix fine that is why we are having 3 loops in this case first one is the outer loop is K from 1 to 4 D 1 D 2 D 3 and d 4 fine within this loop when K key value is 1 then this matrix would be generated using this formula and we know this matrix would be generated using 2 loops one is for row and one is for column that is 1 is I my minor one is J fine first of all for each row when I I is also from 1 to 4 and then J is also from 1 to 4 simply I am writing this I'm just I'm not focusing on the syntax for loop fine this is not the syntax of for loop we check out the syntax I'm just telling you generally fine see I is 1 is 4 suppose row so when I is 1 then these values would be generated for calling 1 2 column 1 2 3 & 4 JK value would be 1 2 4 when I is 2 then also four values would be generated and within these loops you would write this formula this formula would be written over here and finals this one is and so this is all about this all pair shortest path problem or you can say floyd-warshall algorithm so see this kind of algorithm is basically it's better to use computing using this find out this kind of algorithm when the graph is dense graph you know each is each vertex is connected with each other for most of the vertex are connected with each other as well as we are having weights negative also in that case it would be better to use this fluid version algorithm but suppose if graph is very sparse graph fine and only positive weights we are having in that case the better choice is use that Lystra algorithm fine so hopefully in the next video I will discuss that - two algorithms well then go by take it

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

Views: 252,818

Rating: 4.871377 out of 5

Keywords: Floyd Warshall Algorithm, sorting algorithms, dijkstra algorithm, shortest path, brute force algorithm, flood fill algorithm, viterbi algorithm, tower of hanoi algorithm, division algorithm, greedy algorithm, id3 algorithm, shortest path algorit, all pair shortest path, dynamic programming, jennys lectures, ugc net, computer science, cse, IT, engineering colleges, GATE computer science preparation, coaching classes, study material, algorithms, data structure

Id: Gc4mWrmJBsw

Length: 31min 23sec (1883 seconds)

Published: Fri Jan 25 2019