## Saturday, 1 March 2014

#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);
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

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

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 !

2. I know this is quality based blogs along with other stuff.
c++ programming

3. You are totally right. This post actually made my day. You can not imagine just how much time I
had spent for this info! Thanks!
hotmail signup