Can someone translate this pseudocode to C++ please? ALGORITHM Warshall(A[1..n,

Question

Can someone translate this pseudocode to C++ please?

ALGORITHM Warshall(A[1..n, 1..n])
//ImplementsWarshall’s algorithm for computing the transitive closure
//Input: The adjacency matrix A of a digraph with n vertices
//Output: The transitive closure of the digraph
R(0) ?A
for k?1 to n do
____for i ?1 to n do
________for j ?1 to n do
____________R(k)[i, j ]?R(k?1)[i, j ] or (R(k?1)[i, k] and R(k?1)[k, j])
return R(n)

and translate this to C++ as well:

ALGORITHM Floyd(W[1..n, 1..n])
//Implements Floyd’s algorithm for the all-pairs shortest-paths problem
//Input: The weight matrix W of a graph with no negative-length cycle
//Output: 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, j ], D[i, k]+ D[k, j]}
return D

Explanation / Answer

// File Name: WarshallsAlgorithmTransitiveCloser.cpp
#include <iostream>
#define VER 4
using namespace std;

// Function to print transitive closer
void printTransitiveCloser(int solution[][VER])
{
cout<<" Transitive closure matrix of the given graph: ";
// Loops till number of nodes for row of the matrix
for (int r = 0; r < VER; r++)
{
// Loops till number of nodes for column of the matrix
for (int c = 0; c < VER; c++)
cout<<solution[r][c]<<" ";
cout<<endl;
}// End of for loop
}// End of function

// Function to implement Warshall's algorithm for transitive closure of graph[][]
void findTransitiveClosure(int graph[][VER])
{
/* solution[][] will be the output matrix that will finally have the
shortest distances between every pair of vertices */
int solution[VER][VER], r, c, t;

// Initialize the solution matrix same as input graph matrix.
// Loops till number of nodes for row of the matrix
for (r = 0; r < VER; r++)
// Loops till number of nodes for row of the matrix
for (c = 0; c < VER; c++)
// Assigns each element of the graph matrix to solution matrix
solution[r][c] = graph[r][c];

/* Add all vertices one by one to the set of solution vertices.
---> Before start of a loop, the reachability values for all pairs of vertices such that the reachability values
consider only the vertices in set {0, 1, 2, .. t - 1} as solution vertices.
----> After the end of a loop, vertex no. t is added to the set of solution vertices and the set becomes {0, 1, .. t} */

// Loops till number of vertices
for (t = 0; t < VER; t++)
{
// Loops till number of vertices to pick all vertices as source one by one
for (r = 0; r < VER; r++)
{
// Loops till number of vertices to pick all vertices as destination for the above picked source
for (c = 0; c < VER; c++)
{
// Checks if vertex k is on a path from r to c, then the value of solution[r][c] is 1
solution[r][c] = solution[r][c] || (solution[r][t] && solution[t][c]);
}// End of inner for loop
}// End of outer for loop
}// End of extremely outer for loop

// Calls the function to print the shortest distance matrix
printTransitiveCloser(solution);
}// End of function

// main function definition
int main()
{
// Creates a adjacency matrix graph
int graph[VER][VER] = { {1, 0, 0, 0},
{0, 1, 1, 0},
{1, 1, 0, 0},
{1, 0, 0, 1}
};

// Calls the function to find transitive closure
findTransitiveClosure(graph);
return 0;
}// End of main function

Sample Output:

Transitive closure matrix of the given graph:
1 0 0 0
1 1 1 0
1 1 1 0
1 0 0 1

------------------------------------------------------------------

// File Name: FloydsAlgorithmAllPairsShortestPaths.cpp
#include<iostream>
#include<iomanip>
// Defines number of vertices in the graph
#define VER 4
// Define Infinite as a large enough value. This value will be used for vertices not connected to each other
#define INF 99999
using namespace std;

// Function to print all pair short path
void printAllPairShortestPath(int distance[][VER])
{
cout<<" Shortest distances between every pair of vertices ";
// Loops till number of nodes for row of the matrix
for (int r = 0; r < VER; r++)
{
// Loops till number of nodes for column of the matrix
for (int c = 0; c < VER; c++)
{
// Checks if the distance matrix current element is INF then display INF
if (distance[r][c] == INF)
cout<<fixed<<setw(5)<<"INF";
// Otherwise display the value
else
cout<<fixed<<setw(5)<<distance[r][c];
}// End of inner for loop
cout<<endl;
}// End of outer for loop
}// End of function

// Function to implement Floyd 's algorithm for all-pairs shortest path of graph[][]
void findAllPairShortestPath(int graph[][VER])
{
// distance[][] is matrix to store the shortest distances between every pair of vertices
int distance[VER][VER], r, c, t;

// Initialize the solution matrix same as input graph matrix.
// Loops till number of nodes for row of the matrix
for (r = 0; r < VER; r++)
// Loops till number of nodes for row of the matrix
for (c = 0; c < VER; c++)
// Assigns each element of the graph matrix to distance matrix
distance[r][c] = graph[r][c];

/* Add all vertices one by one to the set of distance vertices.
---> Before start of a loop, the shortest distances between all pairs of vertices such that the shortest distances consider only the
vertices in set {0, 1, 2, .. t - 1} as distance vertices.
----> After the end of a loop, vertex no. k is added to the set of distance vertices and the set becomes {0, 1, 2, .. t} */

// Loops till number of vertices
for (t = 0; t < VER; t++)
{
// Loops till number of vertices to pick all vertices as source one by one
for (r = 0; r < VER; r++)
{
// Loops till number of vertices to pick all vertices as destination for the above picked source
for (c = 0; c < VER; c++)
{
// Checks ff vertex t is on the shortest path from r to c, then update the value of disttance[r][c]
if (distance[r][t] + distance[t][c] < distance[r][c])
distance[r][c] = distance[r][t] + distance[t][c];
}// End of inner for loop
}// End of outer for loop
}// End of extremely outer for loop

// Calls the function to print the shortest distance matrix
printAllPairShortestPath(distance);
}// End of function

// main function definition
int main()
{
// Creates a adjacency matrix graph
int graph[VER][VER] = { {0, 19, INF, INF},
{INF, 0, 3, INF},
{7, INF, 2, INF},
{INF, INF, INF, 8}
};
// Calls the function to find all pair shortest path
findAllPairShortestPath(graph);
return 0;
}// End of main function

Sample Output:

Shortest distances between every pair of vertices
0 19 22 INF
10 0 3 INF
7 26 2 INF
INF INF INF 8

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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