Hello friends my name is Tushar and today we're going to talk about floyyd warshall all pair
shortest path algorithm.
So you're given a directed or undirected graph.Floyd Warshall algorithm
is used to find the minimum distance between all pairs of vertices in this graph.
Floyd Warshall algorithm is a dynamic programming algorithm .It works with
negative weight edges on the graph and with variation it can also detect
negative weight cycle in the graph. There are many applications of Floyd Warshall
algorithm like clean's algorithm or transitive closure or widest path in
the graph. So next let's see how this algorithm works.
So we are going to apply Floyd Warshall on this directed graph here. First thing we do is
we take 2 two-dimensional matrices,the size of the matrix is going to be same
as the total number of vertices.
So here we have total 4 vertices.So the size will be 4X4. Then
we go through all the edges and put their value in this distance matrix. So
distance matrix is going to store the minimum distance found so far between 2
vertices.
So for the edges if there is, so say there is an edge between 0 to 2 and this
distance is 6 so 0 to 2 will be 6.
Similarly there is an edge 1 to 2 and distance is - 2 so 1 to 2 will be
-2. Also this path is going to be used to regenerate the minimum path,
minimum distance path between 2 vertices.
So initially if there's a path between 0 to 2 so then 0 to 2 so we're gonna
put 0 here,so the start of the edge and so there's a path between 1 to 2 so
we're going to put 1 here and for all the paths which doesn't exist we're gonna
put infinities and 0 to 0,1 to 1,2 to 2 and 3 to 3 is going to be 0 and here I'm just
going to put 'n' indicating that there is no path available right now between 2
vertices.
So then we're going to have 3 for loops,
'k' going from 0 to 2,0 to 3, 'i' going from 0 to 3 and 'j' going from 0 to 3 and
every time we're going to
check this, if d[i][j] is greater than d[i][k] plus d[k][j] then distance of i,j
will become distance of i,k plus distance of k,j.
So basically checking for every pair of vertices
do we get a shorter distance by going through k and k ranges from 0 to 3 so
so basically in effect we are doing 3 for loops and the total number of operations
will be 4x4x4 which is 64. So we're going to do this check 64 times.
So to save one time I have pre-written the 16 of those checks
So basically for k equal to 0, i equal to 0,i equal to 1, i equal to 2 and i equal to 3 and
j,0,1,2,3.
So we're going to quickly do the checks and update this matrix
if we satisy this condition. So let's run through this example very quickly
Initially k is 0 so what we're checking is for every pair of vertices is
going to go through k which is vertex 0 going to give a shorter distance or not.
So we have in total 16 such combinations because we have 4 vertices in this graph.
So for every combination
we're going to check is going through k,0 vertex 0 going to give a shorter
distance or not.
So this format here is d[i][j] is greater than d[i][k] + d[k][j].
So basically we're doing this check and seeing if d[i][j] is greater than d[i][k] + d[k][j].If
yes then we update the distance to be that distance. So 0 is not going to be
greater than 0 plus 0, so this is not true
3 is not going to be greater than 0 plus 3, so this is not true
6 is not going to be greater than 0 plus 6, so this is not true
and this is not true.So,so far going through 0 vertex is,has not given a
shorter distance. So once we are done iterating through all the values of j we go
here and increment our i by 1. So k continues to be 0,i increments by 1
and then again we're going to go through all values of j. So infinity is greater than
infinity plus 0,it's not. 0 is greater than infinity plus 3, it's not.
- 2, is -2 greater than infinity plus 6, it's not. Is infinitely greater than
infinity plus 15,it's not. So now again we increment our i by 1 more so i
becomes 2, k continues to be 0 and again we're going to set our 0
let's set our j from 0 to 3.So is i,j greater than i,k plus k,j.
So is 2, infinity greater than infinity plus 0, no.Is 2,1 i,j greater than k,j plus
i,k
plus k,j, so again no. Is 2,2 greater than 2,0 plus 0,2, so 0 is not greater than infinity
plus 6 and 2 is not greater than infinity plus 15.
So finally our i becomes 3,k continues to be 0 and again j is going to go from 0 to 3.
Is 1 greater than 1 plus 0, no.Is infinity greater than 1 plus 3,
Yes.
infinity is greater than 1 plus 3. So what we're going to do is
we're gonna to go to this place 3,1 so 3,1 and set this distance to be 1 plus 3
4.
So basically saying d[i][j] is equal to d[i][k] plus d[k][j] and in here i'm going to set
path[i][j] to path[k][j]. So 3,0 will become k,j so 0,1 so whatever the value here
it becomes here.
So what happened was before k was introduced,k,0 was introduced
there was no path between 3 to 1 which is why that value here was
infinity. This value here was infinity but now going through vertex 0 we have a path
of length 4,1 plus 3,4 which is why the new distance between 3 to 1 is 4
and we are also going to indicate that we're going to go via 0 which is why this
value here is 0. Again coming back here, is infinity greater than 1 plus 6,yes.
So again we're going to go through 3,2,update this distance to 7 and then we're gonna go to 3,2
update this distance to, update this path to 0 because we are going via 0 and again
this condition was satisfied and as you can see before 0 was there
there was no path between 3 to 2 but once 0 got introduced there's a path going from
3 to 2 via 1
via this path so 1 plus 6 which is 7 and we are indicating that we are reaching through 0.
Finally is 0 greater than 1 plus 15,no.
So this is not true. So this is all the iterations for k equal to 0.
Next we're going to imcrement our k to 1 and see if we can find a better
path going via vertex 1. So now our k is one and we have updated all the values
accordingly.
So we are still looking for d[i][j],is it greater than d[i][k] + d[k][j].
So is 0 greater than 3 plus infinity, no.Is 3 greater than 3 plus 0,no. Is 6 greater than
3-2,yes.
6 is greater than 1. So what we're gonna do is, we're gonna
go to 0 to 2
and update this value to be 3 - 2 which is 1 and we're going to go to
this path and set this value to be whatever is the value at path[1][2]. So
path[1][2] is 1. So this value becomes 1.
So basically what happened was now that we're going through vertex 1, we had
this path to reach 2 and the distance was 6
but if you go via 1 we can reach
from 0 to 2 in distance 3-2,1 which is why this distance is 1
and we're indicating that to reach from 0 to 2 we go via 1.
So this is true.
Is 15 greater 3 plus infinity,no.So now we increment our
i by 1 and repeat the same process for j from 0 to 3. Is infinitely greater
than 0 plus infinity,no. Is 0 greater than 0 plus 0,no.
Is -2 greater than 0-2,no.Is infinity greater than 0 plus infinity no.Then we're going
to come here,i equal to 2,repeat the same process.No,no,0 greater than,no.2
greater than infinity plus infinity,no.
And finally for i equal to 3,we again repeat j 0 to 3. Is 1 greater
than 4 plus infinity,no. Is 4 greater than 4 plus 0,no. Is 7
greater than 4-2,
yes.7 is greater than 4-2.
So what we're going to do is we're gonna go to 3,2, 3,2
and here we're gonna set the value 4-2,2.
So this value now becomes 2
and then we're gonna go to 3,2 and set this value to be whatever is the value at 1,2.
Value at 1,2 is 1. So this value becomes 1. So again basically we had,we
found a shorter distance to reach,we a shorter distance to reach 2 from
3.
So before we were taking this distance via 3 to 0 to 2
but now we found a shorter distance which is 3 to
0 to 1 to 2. which is what we are reflecting here and here.
So next let's check the last one. Is 3,3 greater than 3,1 plus 1,3, no.
So 4 plus, 0 greater than 4 plus infinity, no.
So now we are done with i, now we are done with k equal to 1. So next what we're
going to do is we're going to increment by k by one more and repeat the same
process.
So let's do that quickly. So we're repeating the process for k equal to 2.Is
0 greater than 1 plus infinity,no. Is 3 greater than 1 plus infinity,no.
Is 1 greater than 1 plus 0,no. Is 15 greater than 1 plus 2,yes.15 is
greater than 1 plus 2. So we go to 0 to 3,15 set this value to be 1 plus 2 which is
3 and then we go to 0 to 3 and set this value to be path[2][3].
So path[2][3] is 2.So set this value to be 2.
So path[i][j] becomes path[k][j]. So basically whatever is at 2,3
comes at 0 to 3.Then moving on for i equal to one,is infinity greater
than -2 plus infinity,no. This infinity indicates that there is no path
from 0 to 2 which means that you cannot use this edge
so you cannot use 2 as an intermediate between 1 and 0. Is 1,1 greater than
-2 plus infinity,no.Is -2 greater than -2 plus 0,no. Is
infinity greater than -2 plus two,yes.Infinity is greater.So we go
to 1,3,
so we go to 1,3, set this value to be 0 and then we go to 1,3 and set this value
to be whatever is at 2,3.So 2,3 is again 2.So this becomes 2.
So what happened was before there was no path between 1 to 3 and now that we're going through 2
there is a path between 1 to 3
and the distance is 0. Next let's move on for i equal to 2. Is infinity greater
than 0 plus infinity,
no. Is infinity greater than 0 plus infinity,no. Is 0 greater than 0 plus 0,no. Is 2
greater than 0 plus 2,no.
Finally for i equal to 3, Is 1 greater than 2 plus infinity,no. Is 4
greater than 2 plus infinity,no. Is 2 greater than 2 plus 0,no.Is 0
greater than 2 plus 0,no.
So this is how it looks for k equal to 2 iterations.
So next,finally lets do the k equal to 3 iterations.
So repeating this process for k equal to 3 and checking for every pair
of vertices, is there going to be a shorter path going via 3 or not.
So 0 is not greater than 3 plus 1.3 is not greater than 3 plus 4.
1 is not greater than 3 plus 2 and 3 is not greater than 3 plus 0.Infinity is greater
than 0 plus, 0 plus 1.So we go to 1 to 0,1 to 0 and set this value to be 0
plus 1 which is 1 and then we go to 1 to 0 here and set this value to be whatever
is the value at 3,0.
So the value at 3,0 is 3 so this value becomes 3. 0 is not greater than 0 plus 4.
-2 is not greater than 0 plus 2.0 is not greater than 0 plus 0.
So for going i equal to 2 infinity is greater than 2 plus 1 so we go to
2,0 and set this value to be 2 plus 1 which is 3 and then we go to 2,0 in
this path matrix and set this value to be whatever is at
3,0 so at 3,0 we have 3 so this value becomes 3.Infinity is greater
than 2 plus 4,yes.
So we again go to 2,1 and set this value to be
6 and we go to 2,1 and set this value to be whatever is at 3,1.
So at 3,1 we have value 0 so this becomes 0.0 plus 2 is not and 2 plus 2 is not
greater than,is greater than 0.2 is not greater than 2 plus 0.
Finally for i equal to 3 1 is not greater than 1 plus 0,4 is not greater than
0 plus 4.2 is not greater than this and this is not greater than this.So this is it.
This is our shortest distance matrix.
So for example the shortest distance between 0 to 3 is, 0 to 3 is 3 and the shortest
distance between,say 3 to 2 is, 3 to 2 is 2.
So let's see how we are going to construct the path.
So let's say I was trying to construct what is the shortest path between 0 to
3.
So we're looking for the shortest path between 0 to 3. So first we go to this
path matrix,go to 3,see what value is there.
So this value is going to be right before 3. So we are reaching 3
via
2. Then we go to 0 to 2 because this value is 2 so we go to 0 to 2 and this value is going to be
right, so this value is 1.So 1 is going to be right before 2 and then we
go to 0 to 1 and we found this source value. So this is the path,we reach 3
via 0.So 0 to 1,1 to 2 and 2 to 3 and the distance here is 3-2,1 plus 2,3-2
is 1 plus 2 is 3 and that is the distance between 0 to 3.
Let's look at another example.Let's see what what is the minimum path,what is
minimum path from 3 to 2.
So you go to,you go to 3,2 so 3,2 is 1.So we're looking for minimum path between 3
to 2. So you go to 3 to 2,
this value is 1 so 1 is going to be right before 2.Then you go to 3
to 1,
so this value is 0 so 0 is going to be right before 1 and then you go to 3 to 0 and
this value is 3 which is our source.
So to go to 3 to 2,you go to 0,then you go to 1 and then you go to 2 and the
distance here is 1 plus 3,4 minus 2,2 and that is the distance between 3 to
2.
So the time complexity for this algorithm is very easy to calculate.
It's O(v^3). So as I said we are repeating this
we have 3 for loops as we saw we have 3 for loops
and for every for loop we are doing this, this work.
So the total time complexity O(v^3) and the space complexity is
O(v^2).
Finally if you want to check if there's a, if there is a negative weight cycle
or not in the graph
what will happen is if you apply the same algorithm if the values along the
diagonal becomes negative it means that the there is a negative weight cycle in
the graph.In this example
none of the values change from 0 which means that there is no negative weight
cycle in this graph but if there was a negative weight cycle, these values would have
become minus,negative
it would have become a negative number which would tell us that there is a negative
weight cycle in the graph. So finally let's look at the code for this
algorithm.Main function allPaiShortestPath.
It takes in a distance matrix. For distance matrix, ij is the distance of
vertex i to vertex j. If there is no path from i to j then the distance
matrix will store a value infinity. Then we initialise 2 other matrices,distance
and path where distance is going to store the minimum distance of every vertex
from every other vertex in the graph and path is going to be useful to regenerate
the minimum distance path from one vertex to another vertex. We
iterate through the distance matrix and set the value of distance[i][j] to be
distanceMatrix[i][j] and if distance Matrix[i][j] is not infinity and i is not j
then path[i][j]
becomes i otherwise path[i][j] becomes -1 indicating that currently
there is no path from i to j. Then as we discussed in the video we have this
3 for loops,
i,j and k all going from 0 to the total number of vertices in the graph. If
distance[i][k] is infinity or distance[k][j] is infinity which means that there is
no path from i to k or k to j, then we continue otherwise if distance[i][j] is
greater than distance[i][k] plus distance[k][j] then distance[i][j] becomes distance[i][k]
plus distance[k][j] and path[i][j] becomes path[k][j], again as we discussed before
in the video. After we had done doing this for loop distance[i][j] stores the
minimum distance from every vertex to every other vertex. Once we're done with
the for loop we are going to check if there is no negative weight cycle in the
graph. To do that we again iterate through the distance matrix
diagonally and see if any of the diagonal values is negative. If any of the
diagonal value is negative then it means that there is a negative weight cycle in
the graph and then we throw this exception
otherwise we just return the distance matrix. Also if you want to print
the path from one vertex to another vertex you can use this method, you
can use this method printPath.
It takes in this path matrix and here we are going to print the minimum distance
path from vertex 3 to vertex 2.
So here i is three and j is two and then wethe initialize stack and add j into
the stack and then go into this while loop and then j comes path[i][j]. If j is
-1 it means that there is no path possible from i to j which is when we
return
otherwise we add j to the stack and keep going into this for look till i become j
and as soon as i becomes j we break out of the for loop and print contents of the
stack which is the path from i to j. So this is all I have to talk about floyd
warshall all pair shortest path algorithm. The link to this code is in the
description section of the video. Please like this video, share this video,comment
on this video,
like my facebook page and check out my github link. Thanks again for watching
this video.