/*
The following program is an implementation of
Dijkstra's algorithm in C language.
To know about the algo check the link :
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
The default number of nodes are 7,however the user can
change the maxnodes field.
*/
#include<unistd.h>
#include<stdlib.h>
#define infinity 20
#define maxnodes 7
#define member 1
#define nonmember 0
void djalgo(int cost[maxnodes][maxnodes],int s,int t,int *pd,int precede[]){
int distance[maxnodes],perm[maxnodes];
int current,i,j,k,dc;
int smalldist,newdist,curr,prev;
for(i=0;i<maxnodes;i++){
perm[i]=nonmember;
distance[i]=infinity;
}
perm[s]=member;
distance[s]=0;
current=s;
while(current!=t){
smalldist=infinity;
dc=distance[current];
for(i=0;i<maxnodes;i++){
if(perm[i]==nonmember)
{
newdist=dc+cost[current][i];
if(newdist<distance[i])
{distance[i]=newdist;
}
if(distance[i]<smalldist){
smalldist=distance[i];
k=i;
}
}
} precede[k]=current;
current=k;
perm[current]=member;
*pd=distance[t];
}
int path[maxnodes],pos=1;
path[0]=t;
printf("\nThe Path is :");
curr=t;
prev=precede[t];
while(curr!=s)
{ if(cost[prev][curr]==distance[curr]-distance[prev]){
printf("%d<-",path[pos-1]);
path[pos++]=prev;
curr=prev;
prev=precede[curr]; }
else
prev=precede[prev];
}
printf("%d",s);
}
void main(){
int i,j,s,t;
int precede[maxnodes],pd;
/*
printf("\nEnter weight matrix:");
for(i=0;i<maxnodes;i++)
{ printf("Enter For Node %d ",i);
for(j=0;j<maxnodes;j++)
scanf("%d",&iost[i][j]);
}*/
int cost[maxnodes][maxnodes]={{20,20,20,8,2,20,20},
{7,20,1,20,20,20,20},
{3,20,20,20,4,3,20},
{2,20,20,20,1,20,20},
{20,20,20,20,20,20,2},
{20,20,20,10,4,20,7},
{20,20,20,2,20,20,20}
};
printf("Enter the starting and endng node:");
scanf("%d%d",&s,&t);
for(i=0;i<maxnodes;i++){
printf("\n");
for(j=0;j<maxnodes;j++)
printf("%d ",cost[i][j]);
}
djalgo(cost,s,t,&pd,precede);
printf("\nThe shortest dist is %d",pd);
}
No comments:
Post a Comment