n this Program be broken into: dijkstra.h main.cpp dijkstra.cpp include #include using namespace std; #define INFINITY 9999 #define max 5 void dijkstra(int G[max][max],int n,int startnode); int main() { int G[max][max]={{0,3,1,0,0
Can this Program be broken into:
dijkstra.h
main.cpp
dijkstra.cpp
include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
int G[max][max]={{0,3,1,0,0}, {0,0,0,3,1}, {0,1,0,0,4}, {0,0,0,0,0}, {0,0,0,2,0}};//adjacency matrix of given graph
int n=5;//number of nodes=5
int u=0;
dijkstra(G,n,u);//calling the dijkstra function
return 0;
}
//implementation of dijkstra algorithm
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;//initially cost of each edge is assigned to infinity
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"Path(0"<<"->"<<i<<"):";
cout<<"Minimum cost="<<distance[i]<<",";
cout<<"Route="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
cout<<"\n";
}
}
Step by step
Solved in 3 steps
