Floyd Warshall Algorithm / All pair shortest path
The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.
formulas used in algorithm:
d[i][j]=d[i][k]+d[k][j];
where i , j are the source and destination
k is the vextex which should be included while going from i to j.click to download the code
Example:
Input:
graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0} }
which represents the following graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3
Note that the value of graph[i][j] is 0 if i is equal to j
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.
Output:
Shortest distance matrix
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
code :
#include<iostream> using namespace std; int main() //main function { int V; cout<<"enter the number of the vertex"; cin>>V; int graph[V][V],d[V][V]; //graph is a 2-d matrix which stores the adjacency matrix of the graph g. cout<<"enter nine's in case of non infinity\n"; cout<<"enter matrix\n"; for(int i=0;i<V;i++) { for(int j=0;j<V;j++) { cin>>graph[i][j]; } } for(int i=0;i<V;i++) //copying the graph into another matrix d; { for(int j=0;j<V;j++) { d[i][j]=graph[i][j]; } } for(int k=0;k<V;k++) { for(int i=0;i<V;i++) { for(int j=0;j<V;j++) { if(d[i][j]>d[i][k]+d[k][j]) //comparing if the prior d[i][j] is greater than than the value that includes vertex k. { d[i][j]=d[i][k]+d[k][j]; } } } } cout<<"\ngraph is\n"; //printing the matrix. for(int i=0;i<V;i++) { for(int j=0;j<V;j++) { if(d[i][j]>=9999) //9999 indicates the infinity. { cout<<"INF"<<" "; } else { cout<<d[i][j]<<" "; } } cout<<"\n"; } }
