This is a C++ Program to implement the Floyd Warshall Algorithm using Dynamic Programming technique.
Find shortest distance between each pair of vertices in the given graph. This problem is also known as All pairs shortest path problem.
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.
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:
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
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.
//Floyd warshall algorithm
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,k;
int n,e;
int s,d,w;
cout<<"Enter the number of vertices ";
cin>>n;
//adjacency matrix
//initialized to infinity
vector<vector<int> > distMat(n,vector<int>(n,INT_MAX));
for(i=0;i<n;i++)
{
//distance of verter i from itself is always zero
distMat[i][i]=0;
}
cout<<"Enter the number of edges ";
cin>>e;
cout<<"Enter the src, dest and weight of each edge"<<endl;
for(i=0;i<e;i++)
{
cin>>s>>d>>w;
//add to the adjacency list
distMat[s-1][d-1]=w;
}
//now, we have the adjacency matrix
//we will create n matrices from this considering a vertex as an intermediate vertex
//intermediate
for(k=0;k<n;k++)
{
//source
for(i=0;i<n;i++)
{
//destination
for(j=0;j<n;j++)
{
if(distMat[i][k]!=INT_MAX &&
distMat[k][j]!=INT_MAX &&
distMat[i][k]+distMat[k][j]<distMat[i][j])
{
distMat[i][j]=distMat[i][k]+distMat[k][j];
}
}
}
}
cout<<endl<<"The all pairs shortest distance matrix is "<<endl;
cout<<" ";
for(i=0;i<n;i++)
{
printf("%6d",i+1);
}
cout<<endl;
for(i=0;i<6*n;i++)
{
cout<<"_";
}
cout<<"_______"<<endl;
for(i=0;i<n;i++)
{
printf("%5d |",i+1);
for(j=0;j<n;j++)
{
if(distMat[i][j]==INT_MAX)
printf(" INF");
else
printf("%6d",distMat[i][j]);
//cout<<distMat[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
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.
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.
- Practice Design & Analysis of Algorithms MCQ
- Practice Computer Science MCQs
- Practice Programming MCQs
- Check Data Structure Books
- Check Programming Books