Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Can anyone help me? I don't know why its not running. This is the link to repl.it https://repl.it/join/wpgmtemo-teptaikorn #include #include #include #define INFINITY 9999 #define

Can anyone help me? I don't know why its not running. This is the link to repl.it

https://repl.it/join/wpgmtemo-teptaikorn

#include

#include

#include

#define INFINITY 9999

#define MAX 100

void dijkstra(int G[MAX][MAX],int n,int startnode);

int main(){

int G[MAX][MAX],n=0,u,c=0,k=1,num;

int T[MAX*MAX], flag = 0;

char ch;

printf(" Enter the adjacency matrix: ");

while(k){

while (1){

scanf("%d%c", &num, &ch);

T[c++] = num;

if (ch == ' '){

if(flag==0){

n = c;

}

break;

}

}

if(flag==0){

flag = 1;

k = n-1;

}else{

k--;

}

}

k = 0;

for(int i=0;i

for(int j=0;j

G[i][j] = T[k++];

}

}

//Uncomment this block to print the matrix

for(int i=0;i

for(int j=0;j

printf("%d ",G[i][j]);

printf(" ");

}

printf(" Enter the starting node:");

scanf("%d",&u);

dijkstra(G,n,u);

return 0;

}

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;

//pred[] stores the predecessor of each node

//count gives the number of nodes seen so far

//create the cost matrix

for(i=0;i

for(j=0;j

if(G[i][j]==0 && i!=j)

cost[i][j] = INFINITY;

else

cost[i][j]=G[i][j];

//initialize pred[],distance[] and visited[]

for(i=0;i

{

distance[i]=cost[startnode][i];

pred[i]=startnode;

visited[i]= 0;

}

distance[startnode]=0;

visited[startnode]=1;

count=1;

while(count<=n)

{

mindistance = INFINITY;

//nextnode gives the node at minimum distance

for(i=0;i

if(distance[i] < mindistance)

{

mindistance=distance[i];

nextnode=i;

}

//check if a better path exists through nextnode

visited[nextnode]=1;

for(i=0;i

if(!visited[i])

if(mindistance+cost[nextnode][i] <= distance[i])

{

distance[i]=mindistance+cost[nextnode][i];

pred[i]=nextnode;

}

count++;

}

//print the path and distance of each node

for(i=0;i

if(i!=startnode)

{

printf(" Distance of node%d=%d",i,distance[i]);

printf(" Path=%d",i);

j=i;

do

{

j=pred[j];

printf("<-%d",j);

}while(j!=startnode);

}

}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Fundamentals Study Guide

Authors: Dr. Sergio Pisano

1st Edition

B09K1WW84J, 979-8985115307

More Books

Students also viewed these Databases questions