#define INFINITY 9999
#include <stdio.h>
#include <conio.h>
#define MAX 10
void dijikstra(int G[MAX][MAX],int n, int startnode);
void main()
{ int G[MAX][MAX],i,j,n,u;
clrscr();
printf("\nEnter no. of vertices : ");
scanf("%d",&n);
printf("\nEnter adjacency matrix : ");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
printf("\nEnter the starting node : ");
scanf("%d",&u);
dijikstra(G,n,u);
getch();
}
void dijikstra(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<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
//initialize
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 ;
// nextnode is the node at minimum distance
for(i=0;i<n;i++)
if(distance[i] < mindistance && !visited[i])
{ mindistance=distance[i];
nextnode=i;
}
//check if a better path exist through nextnode
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++;
}
//print the path and distance of each node
for(i=0;i<n;i++)
if(i!=startnode)
{ printf("\n Distance of %d = %d ",i,distance[i]);
printf("\nPath = %d ",i);
j=i;
do {
j=pred[j];
printf("<- %d ",j);
}while(j!=startnode);
}
}
OUTPUT:-
Enter no. of vertices : 4
Enter adjacency matrix :
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
Enter the starting node : 1
Distance of 0 = 1
Path = 0 <- 1
Distance of 2 = 1
Path = 2 <- 1
Distance of 3 = 2
Path = 3 <- 0 <- 1
Hello, I'm doing the same algorithm but in the other side, I mean I would have at the end of this algorithm the longest way between all nodes. I've modified conditions and it works for all nodes except between the first and the last node. Can you help ? Please !
ReplyDeleteI know this is quality based blogs along with other stuff.
ReplyDeletec++ programming
Thanks
ReplyDeleteYou are totally right. This post actually made my day. You can not imagine just how much time I
ReplyDeletehad spent for this info! Thanks!
hotmail signup