Have to find the Transitive Closure in Graph.h & All Pairs Shortest path in Floy

Question

Have to find the Transitive Closure in Graph.h & All Pairs Shortest path in Floyds. Stuck on the coding on what goes on the inside of the for loops. I have started but I am confused on how to finish these two algorithms out.

the next matrix in sequence (8.12) can be written over its predecessor. ALGORITHM Floyd (W[1..n, 1...nl) llImplements Floyd's algorithm for the all-pairs shortest-paths problem Input: The weight matrix W of a graph with no negative-length cycle lloutput: The distance matrix of the shortest paths' lengths D W //is not necessary if W can be overwritten for k 1 to n do for i 1 to n do for j 1 to n do D[i, j] min D[i, jl, Dli, kl+ D[k, j]) return D Obviously, the time efficiency of Floyd's algorithm is cubic as is the

Explanation / Answer

Floyds Algorithem code in C++

#include <iostream>
using namespace std;
void floyds(int d[20][20],int nodes)
{
int i, j, k;
for (k = 0; k < nodes; k++)
{
for (i = 0; i < nodes; i++)
{
for (j = 0; j < nodes; j++)
{
if ((d[i][k] * d[k][j] != 0) && (i != j))
{
if ((d[i][k] + d[k][j] < d[i][j]) || (d[i][j] == 0))
{
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
}
for (i = 0; i < nodes; i++)
{
cout<<" Minimum Cost to the all nodes from :"<<i<<endl;
for (j = 0; j < nodes; j++)
{
cout<<d[i][j]<<" ";
}

}
}
int main()
{
int b[20][20],nodes;
cout<<"Enter number of nodes graph contain"<<endl;
cin>>nodes;
cout<<"ENTER VALUES OF GRAPH (ADJACENCY MATRIX)"<<endl;
for (int i = 0; i < nodes; i++)
{
cout<<"enter values from "<<(i+1)<<" node to all nodes :"<<endl;
for (int j = 0; j < nodes; j++)
{
cin>>b[i][j];
}
}
floyds(b,nodes);

}

Ouput:-

Enter number of nodes graph contain
3
ENTER VALUES OF GRAPH (ADJACENCY MATRIX)
enter values from 1 node to all nodes :
0 2 5
enter values from 2 node to all nodes :
3 0 5
enter values from 3 node to all nodes :
8 4 0

Minimum Cost to the all nodes from :0
0 2 5
Minimum Cost to the all nodes from :1
3 0 5
Minimum Cost to the all nodes from :2
7 4 0

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.