Floyd Warshall Algorithm  

Difficulty Level Medium
Frequently asked in Samsung
Dynamic Programming Graph Shortest Path

Floyd Warshall Algorithm is a method to find the shortest path between two vertices for all the pairs of vertices. We apply this method to a weighted graph with no negative cycles. We apply some operations to the V*V matrices which initially store large value(infinite) in each cell. Here we use the Dynamic Programming approach to find the shortest path between all the possible pairs of vertices in a given graph. We solve this problem by taking a sequence of decisions. Let’s understand this by an example.

Floyd Warshall AlgorithmPin

Working of Floyd Warshall Algorithm  

Step-1

Make a matrix A0 which stores the information about the minimum distance of path between the direct path for every pair of vertices. If there is no edge between two vertices, then we initialize the distance of path in that case as infinity(very big number). See all the steps on the bases of the above-directed graph.

Floyd Warshall AlgorithmPin

Please click Like if you loved this article?

Step-2

In this step, we use Ao matrix and find the shortest path via 1 as an intermediate node. Here all the path that belongs to 1 remain unchanged in the matrix A1. Here one more thing which is important, there is no self-loop so the diagonals are 0 always.

See also
Priority Queue using doubly linked list

A1[1,1]=0, A1[2,2]=0, A1[3,3]=0, A1[4,4]=0.

A1[1,2], A1[1,3], A1[1,4], A1[2,1], A1[3,1], A1[4,1] are remain same as in matrix A0.

A1[2,3]= min(A0[2,3], A0[2,1]+A0[1,3]) = Infinity.

A1[2,4]= min(A0[2,4], A0[2,1]+A0[1,4]) = 15. Similarly find the others values. Final matrix A1 is look like:

Floyd Warshall AlgorithmPin

Step-3 

In this step, we use A1 matrix and find the shortest path via 2 as an intermediate node. Here all the path that belongs to 2 remain unchanged in the matrix A2. Here one more thing which is important, there is no self-loop so the diagonals are 0 always.

A2[1,1]=0, A2[2,2]=0, A2[3,3]=0, A2[4,4]=0.

A2[1,2], A2[3,2], A2[4,2], A2[2,1], A2[2,3], A2[2,4] are remain same as in matrix A1.

A2[1,3]= min(A1[1,3], A1[1,2]+A1[2,3]) = 5.

A2[1,4]= min(A1[1,4], A1[1,2]+A1[2,4]) = 7. Similarly find the others values. Final matrix A2 is look like:

Pin

Step-4 

In this step, we use A2 matrix and find the shortest path via 3 as an intermediate node. Here all the path that belongs to 3 remain unchanged in the matrix A3. Here one more thing which is important, there is no self-loop so the diagonals are 0 always.

A3[1,1]=0, A3[2,2]=0, A3[3,3]=0, A3[4,4]=0.

A3[1,3], A3[2,3], A3[4,3], A3[3,1], A3[3,2], A3[3,4] are remain same as in matrix A2.

Please click Like if you loved this article?

A3[1,2]= min(A2[1,2], A2[1,3]+A2[3,2]) = 3.

A3[1,4]= min(A2[1,4], A2[1,3]+A2[3,4]) = 6. Similarly find the others values. Final matrix A3 is look like:

Pin

Step-5 

In this step, we use A3 matrix and find the shortest path via 4 as an intermediate node. Here all the path that belongs to 4 remain unchanged in the matrix A4. Here one more thing which is important, there is no self-loop so the diagonals are 0 always.

See also
Transpose Graph

A4[1,1]=0, A4[2,2]=0, A4[3,3]=0, A4[4,4]=0.

A4[1,4], A4[2,4], A4[3,4], A4[4,1], A4[4,2], A4[4,3] are remain same as in matrix A3.

A4[1,2]= min(A3[1,2], A3[1,4]+A3[4,2]) = 3.

A4[1,3]= min(A3[1,3], A3[1,4]+A3[4,3]) = 5. Similarly find the others values. Final matrix A4 is look like:

Pin

A4 matrix is our final matrix which tells us the minimum distance between two vertices for all the pairs of vertices.

Algorithm For Floyd Warshall Algorithm  

Step:1 Create a matrix A of order N*N where N is the number of vertices.
Step:2 For i in range 1 to N:
       i) For j in range 1 to N:
          a) For k in range 1 to N:
             A^(k)[j,k]= MIN(A^(k-1)[j,k],A^(k-1)[j,i]+A^(K-1)[i,k]).
Step:3 Print the array A.

Implementation For Floyd Warshall Algorithm  

/*C++ Implementation of Floyd Warshall Algorithm.*/ 
#include<bits/stdc++.h> 
using namespace std; 
#define INF 1000000009
int main() 
{
    /*input values*/
    int nodes,edges;
    cin>>nodes>>edges;
    int a[nodes+1][nodes+1];
    memset(a,INF,sizeof(a));
    /*create matrix A0*/
    for(int i=0;i<edges;i++)
    {
        int x,y,weight;
        cin>>x>>y>>weight;
        a[x][y]=weight;
    }
    /*All the diagonals values are 0*/
    for(int i=1;i<=nodes;i++)
    {
        a[i][i]=0;
    }
    /*find the final matrix A^n*/
    for(int i=1;i<=nodes;i++)
    {
        for(int j=1;j<=nodes;j++)
        {
            for(int k=1;k<=nodes;k++)
            {
                a[j][k]=min(a[j][k],a[j][i]+a[i][k]);
            }
        }
    }
    /*Print the answer(final matrix)*/
    for(int j=1;j<=nodes;j++)
    {
        for(int k=1;k<=nodes;k++)
        {
            cout<<a[j][k]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
4 7
1 2 3
2 1 8
2 3 2
3 4 1
4 1 2
1 4 7
0 3 5 6 
5 0 2 3 
3 6 0 1 
2 5 7 0

Time Complexity  

O(N*N*N) where N is the number of nodes in the given graph. Here we handle the N*N matrix N times so for the overall operation to get the final matrix we run 3 nested loops.

Space Complexity  

O(N*N) where N is the number of nodes in the given graph. We handle a matrix of order N*N to get the final result of the algorithm.

References

Please click Like if you loved this article?