In C++,Write a program that uses Dijkstra's Algorithm to determine the distance and a shortest path from a "Base Node" to every other node in a given weighted (undirected) graph G. A data file is to...

1 answer below »

In C++,Write a program that uses Dijkstra's Algorithm to determine the distance and a shortest path from a "Base Node" to every other node in a given weighted (undirected) graph G. A data file is to contain a list of Cities (think of the City names as labels on the nodes of the graph) and the upper-right triangular portion of a modified adjacency matrix. (In this adjacency matrix, if there is a direct connection between city i and city j, the i,j entry will contain the "distance" between these two cities; otherwise, the i,j entry will be zero.) The City names will be shortened to four (4) letters or less. The user should be prompted to enter the name of the data file and the name (label) for the Base Node, which may be any node in the graph. All distances will be measured, and all shortest paths will begin at this Base Node. The output should consist of: 1) the complete adjacency matrix for the graph 2) for each node (except the Base Node): a) the distance from the Base Node to the current node b) a shortest path from the Base Node to the current node

Answered 5 days AfterOct 25, 2021

Answer To: In C++,Write a program that uses Dijkstra's Algorithm to determine the distance and a shortest path...

Karthi answered on Oct 28 2021

131 Votes

#include
#include
#include
using namespace std;
#define V 5 //Defines total number of vertices in the graph
#define INFINITY 999
int N, M;
int miniDist(int distance[], bool Tset[]) // finding minimum distance
{
int minimum=INT_MAX,ind;

for(int k=0;k<6;k++)
{
if(Tset[k]==false && distance[k]<=minimum)
{
minimum=distance[k];
ind=k;
}
}
return ind;
}
void DijkstraAlgo(int graph[6][6],int src) // adjacency matrix
{
int distance[6]; // // array to calculate the minimum distance for each node
bool Tset[6];// boolean array to mark visited and unvisited for each node

for(int k = 0; k<6; k++)
{
distance[k] = INT_MAX;
Tset[k] = false;
}

distance[src] = 0; // Source vertex distance is set 0

for(int k = 0; k<6; k++)
{
int...

SOLUTION.PDF

In C++,Write a program that uses Dijkstra's Algorithm to determine the distance and a shortest path from a "Base Node" to every other node in a given weighted (undirected) graph G. A data file is to...

Answer To: In C++,Write a program that uses Dijkstra's Algorithm to determine the distance and a shortest path...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment