Use C++ for this code and show every step thanks Develop code using Floyd and Wa

Question

Use C++ for this code and show every step thanks

Develop code using Floyd and Warshall algorithm. Use the graph from the link below:

https://www.youtube.come/watch?v=8TRX85-myD4

The link above shows the working of the Algorithm. Use the logic shown below:

Pseudo code:

Build D and S matrix from the graph

Assume:

                K = Iteration

                I = Total number of columns

                J = Total number of columns

                Display both D and S matrix before the start of the algorithm

                For(K=0; K<4; K++)

                {//START OF 1st for loop

                                for(I = 0; I < 4; I ++)

{ //START of 2nd for loop)

                for(J = 0; J <4; J++)

                {//START of 3rd for loop

                                If(D[I][J]>D[I][K]+D[K][J])

                                {

                                                D[I][J] = D[I][K]+D[K][J]

S[I][J] = S[K][J]

}

}//End of 3rd for loop

                                }//End of 2nd for loop

                }//End of 1st for loop

Display both D and S matrix after the end of the algorithm

Make sure both matrix have the exact same numbers as the one showed up in the link above.

Ask the user the following:

Starting Node

Ending Node

Provide the following

Total cost

Traversal path

Explanation / Answer

#include<iostream>
#define INFINITY 999

using namespace std;

class Dijkstra{
private:
int adjMatrix[15][15];
int predecessor[15],distance[15];
bool mark[15]; //keep track of visited node
int source;
int numOfVertices;
public:
void read();
void initialize();
int getClosestUnmarkedNode();
void calculateDistance();
void output();
void printPath(int);
};
void Dijkstra::read(){
cout<<"Enter the number of vertices of the graph(should be > 0) ";
cin>>numOfVertices;
while(numOfVertices <= 0) {
cout<<"Enter the number of vertices of the graph(should be > 0) ";
cin>>numOfVertices;
}
cout<<"Enter the adjacency matrix for the graph ";
cout<<"To enter infinity enter "<<INFINITY<<endl;
for(int i=0;i<numOfVertices;i++) {
cout<<"Enter the (+ve)weights for the row "<<i<<endl;
for(int j=0;j<numOfVertices;j++) {
cin>>adjMatrix[i][j];
while(adjMatrix[i][j]<0) {
cout<<"Weights should be +ve. Enter the weight again ";
cin>>adjMatrix[i][j];
}
}
}
cout<<"Enter the source vertex ";
cin>>source;
while((source<0) && (source>numOfVertices-1)) {
cout<<"Source vertex should be between 0 and"<<numOfVertices-1<<endl;
cout<<"Enter the source vertex again ";
cin>>source;
}
}


void Dijkstra::initialize(){
for(int i=0;i<numOfVertices;i++) {
mark[i] = false;
predecessor[i] = -1;
distance[i] = INFINITY;
}
distance[source]= 0;
}


int Dijkstra::getClosestUnmarkedNode(){
int minDistance = INFINITY;
int closestUnmarkedNode;
for(int i=0;i<numOfVertices;i++) {
if((!mark[i]) && ( minDistance >= distance[i])) {
minDistance = distance[i];
closestUnmarkedNode = i;
}
}
return closestUnmarkedNode;
}


void Dijkstra::calculateDistance(){
initialize();
int minDistance = INFINITY;
int closestUnmarkedNode;
int count = 0;
while(count < numOfVertices) {
closestUnmarkedNode = getClosestUnmarkedNode();
mark[closestUnmarkedNode] = true;
for(int i=0;i<numOfVertices;i++) {
if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) ) {
if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) {
distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];
predecessor[i] = closestUnmarkedNode;
}
}
}
count++;
}
}


void Dijkstra::printPath(int node){
if(node == source)
cout<<(char)(node + 97)<<"..";
else if(predecessor[node] == -1)
cout<<"No path from

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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