Implement Floyd Warshall algorithm in a weighted directed graph to find all pair shortest paths. Print the all pair shortest paths.
Soda Code:
Code:
#include<iostream>>
using namespace
std;
int
nameArray[100];
void warshall(int
graph[100][100], int n){
for(int m=0; m < n; m++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(graph[i][m] != 666
&& graph[m][j] != 666){
graph[i][j] =
min(graph[i][j], graph[i][m] + graph[m][j]);
}
}
}
}}
int
checkVertexLocation(int u1, int n){
for(int i = 0; i < n; i++){
if(nameArray[i] == u1){
return i;
}
}
}
int main(){
int graph[100][100], w, nvertice, nedge;
int c, s, e;
cout << "Enter number of
Vertices and Edges : ";
cin >> nvertice >> nedge;
for(int i = 0; i < nvertice; i++){
for(int j = 0; j < nvertice; j++){
if(i == j){
graph[i][j] = 0;
} else{
graph[i][j] = 666;
}
}
}
cout << "Enter Vertex name: ";
for(int i = 0; i < nvertice; i++){
cin >> c;
nameArray[i] = c;
}
for(int i = 0; i < nedge; i++){
cout << "Enter source then
destination then weight: ";
cin >> s >> e >> w;
graph[checkVertexLocation(s,
nvertice)][checkVertexLocation(e, nvertice)] = w;
}
warshall(graph, nvertice);
cout << "\n\nshortest path’s
cost of all possible pairs graph is given bellow : \n";
for(int i = 0; i < nvertice; i++){
for(int j = 0; j < nvertice; j++){
if(graph[i][j] != 666){
cout << graph[i][j]
<< "\t\t";
}
else{
cout <<
"Inf\t\t";
}
}
cout << "\n";
}
cout << "\n\nOne By one
distance:\n\n";
for(int i = 0; i < nvertice; i++){
for(int j = 0; j < nvertice; j++){
if(graph[i][j] != 666){
cout << "From "
<< nameArray[i] << " To " << nameArray[j] <<
" is: " << graph[i][j] << "\n";
} else{
cout << "From "
<< nameArray[i] << " To " << nameArray[j] <<
" is: Inf\n";
}
}
}
Output:
Conclusion: Floyd-Warshal performs the same in calculations and in
determining rectangular calculations and frameworks. For phase j ≥ 1, as may be
the case, the rectangular calculation determines the more rapidly related
structure due to the reduction of the sum of the calculations.