Floyd Warshall Algorithm using Dynamic Programming

This is a C++ Program to implement the Floyd Warshall Algorithm using Dynamic Programming technique.

Problem Description

Find shortest distance between each pair of vertices in the given graph. This problem is also known as All pairs shortest path problem.

Problem Solution

One solution to this problem is to apply Dijkstra algorithm for all vertices. But if the graph contain negative weight edges, Dijkstra algorithm could not be applied.

In that case, we have Floyd Warshall algorithm. We start with the adjacency matrix of the graph. If there is no path from vertex i to j, the cell(i,j) in the matrix will be initialized to INFINITY. And each cell(i,i) will be initialized to 0.

Then, we consider every vertex(one by one) as an intermediate vertex. For example – if intermediate is vertex i, and we want to reach from vertex j to vertex k, we will first go from vertex i to vertex j and then vertex j to vertex k instead of directly going from j to k.

It is O(V^3) algorithm where V is the number of vertices.

advertisement
advertisement
Expected Input and Output

Case-1:

 
number of vertices=8
number of edges=9
 
Information of all edges(source, destination, weight)
1 2 8
2 3 7
2 4 3
3 5 5
3 6 2
4 7 -4
4 8 6
5 7 -3
6 8 9
 
Expected Result: 
 
The all pairs shortest distance matrix is 
            1     2     3     4     5     6     7     8
_______________________________________________________
    1 |     0     8    15    11    20    17     7    17
    2 |   INF     0     7     3    12     9    -1     9
    3 |   INF   INF     0   INF     5     2     2    11
    4 |   INF   INF   INF     0   INF   INF    -4     6
    5 |   INF   INF   INF   INF     0   INF    -3   INF
    6 |   INF   INF   INF   INF   INF     0   INF     9
    7 |   INF   INF   INF   INF   INF   INF     0   INF
    8 |   INF   INF   INF   INF   INF   INF   INF     0

Case-2:

Note: Join free Sanfoundry classes at Telegram or Youtube
 
number of vertices=5
number of edges=7
 
Information of all edges(source, destination, weight)
1 2 3
1 4 4
2 4 5
3 1 1
3 5 8
4 2 2
4 5 6
 
Expected Result: 
 
The all pairs shortest distance matrix is 
            1     2     3     4     5
_____________________________________
    1 |     0     3   INF     4    10
    2 |   INF     0   INF     5    11
    3 |     1     4     0     5     8
    4 |   INF     2   INF     0     6
    5 |   INF   INF   INF   INF     0

Case-3:

 
number of vertices=4
number of edges=8
 
Information of all edges(source, destination, weight)
1 2 8
2 3 7
3 4 6
4 1 5
1 4 4
4 3 3
3 2 2
2 1 1
 
Expected Result: 
 
The all pairs shortest distance matrix is 
            1     2     3     4
_______________________________
    1 |     0     8     7     4
    2 |     1     0     7     5
    3 |     3     2     0     6
    4 |     5     5     3     0
Program/Source Code

Here is source code of the C++ Program to solve All pairs shortest path problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
  1.  
  2. //Floyd warshall algorithm
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int i,j,k;
  9.     int n,e;
  10.     int s,d,w;
  11.  
  12.     cout<<"Enter the number of vertices ";
  13.     cin>>n;
  14.  
  15.     //adjacency matrix
  16.     //initialized to infinity
  17.     vector<vector<int> > distMat(n,vector<int>(n,INT_MAX));
  18.  
  19.     for(i=0;i<n;i++)
  20.     {
  21.         //distance of verter i from itself is always zero
  22.         distMat[i][i]=0;
  23.     }
  24.  
  25.     cout<<"Enter the number of edges ";
  26.     cin>>e;
  27.  
  28.     cout<<"Enter the src, dest and weight of each edge"<<endl;
  29.     for(i=0;i<e;i++)
  30.     {
  31.         cin>>s>>d>>w;
  32.  
  33.         //add to the adjacency list
  34.  
  35.         distMat[s-1][d-1]=w;
  36.     }
  37.  
  38.     //now, we have the adjacency matrix
  39.     //we will create n matrices from this considering a vertex as an intermediate vertex
  40.  
  41.     //intermediate
  42.     for(k=0;k<n;k++)
  43.     {
  44.         //source
  45.         for(i=0;i<n;i++)
  46.         {
  47.             //destination
  48.             for(j=0;j<n;j++)
  49.             {
  50.                 if(distMat[i][k]!=INT_MAX && 
  51.                    distMat[k][j]!=INT_MAX &&
  52.                    distMat[i][k]+distMat[k][j]<distMat[i][j])
  53.                     {
  54.                         distMat[i][j]=distMat[i][k]+distMat[k][j];
  55.                     }
  56.  
  57.             }
  58.         }
  59.     }
  60.  
  61.     cout<<endl<<"The all pairs shortest distance matrix is "<<endl;
  62.  
  63.     cout<<"       ";
  64.  
  65.     for(i=0;i<n;i++)
  66.     {
  67.         printf("%6d",i+1);
  68.     }
  69.  
  70.     cout<<endl;
  71.  
  72.     for(i=0;i<6*n;i++)
  73.     {
  74.         cout<<"_";
  75.     }
  76.  
  77.     cout<<"_______"<<endl;
  78.  
  79.     for(i=0;i<n;i++)
  80.     {
  81.         printf("%5d |",i+1);
  82.         for(j=0;j<n;j++)
  83.         {
  84.             if(distMat[i][j]==INT_MAX)
  85.                 printf("   INF");
  86.  
  87.             else
  88.                 printf("%6d",distMat[i][j]);
  89.             //cout<<distMat[i][j]<<"   ";
  90.         }
  91.  
  92.         cout<<endl;
  93.     }
  94.  
  95.     return 0;
  96. }
Program Explanation

In the main function, we take input for number of vertices and edges in the graph. Then we will take inputs for the information of all edges(source, destination and weight). This information is stored in the adjaceny matrix. Then, the nested loop will calculate all pair shortest paths of the graph. Finally, this matrix will be displayed.

Runtime Test Cases
 
Case-1:
$ g++ floydWarshall.cpp
$ ./a.out
Enter the number of vertices 5 7
Enter the number of edges Enter the src, dest and weight of each edge
1 2 3
1 4 4
2 4 5
3 1 1
3 5 8
4 2 2
4 5 6
 
The all pairs shortest distance matrix is 
            1     2     3     4     5
_____________________________________
    1 |     0     3   INF     4    10
    2 |   INF     0   INF     5    11
    3 |     1     4     0     5     8
    4 |   INF     2   INF     0     6
    5 |   INF   INF   INF   INF     0
 
Case-2:
$ ./a.out
Enter the number of vertices 4  
Enter the number of edges 8
Enter the src, dest and weight of each edge
1 2 8
2 3 7
3 4 6
4 1 5
1 4 4
4 3 3
3 2 2
2 1 1
 
The all pairs shortest distance matrix is 
            1     2     3     4
_______________________________
    1 |     0     8     7     4
    2 |     1     0     7     5
    3 |     3     2     0     6
    4 |     5     5     3     0
 
 
Case-3:
$ ./a.out
Enter the number of vertices 8  
Enter the number of edges 9
Enter the src, dest and weight of each edge
1 2 8
2 3 7
2 4 3
3 5 5
3 6 2
4 7 -4
4 8 6
5 7 -3
6 8 9
 
The all pairs shortest distance matrix is 
            1     2     3     4     5     6     7     8
_______________________________________________________
    1 |     0     8    15    11    20    17     7    17
    2 |   INF     0     7     3    12     9    -1     9
    3 |   INF   INF     0   INF     5     2     2    11
    4 |   INF   INF   INF     0   INF   INF    -4     6
    5 |   INF   INF   INF   INF     0   INF    -3   INF
    6 |   INF   INF   INF   INF   INF     0   INF     9
    7 |   INF   INF   INF   INF   INF   INF     0   INF
    8 |   INF   INF   INF   INF   INF   INF   INF     0

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.