Ash's Blog

IMPLEMENTATION OF DIJKSTRA’S SHORTEST PATH ALGORITHM

Posted on: February 23, 2011

*IMPLEMENTATION OF DIJKSTRA’S ALGORITHM*/
#include
#include
#define maxnode 10
#define perm 1
#define tent 2
#define infinity INT_MAX
typedef struct nodelabel
{
int predecessor;
int length;
int label;
}nodelabel;
int shortpath(a,n,s,t,path,dist)
int a[maxnode][maxnode],n,s,t,path[maxnode],*dist;
{
nodelabel state[maxnode];
int i,k,min,count,rpath[maxnode];
*dist=0;
for(i=1;i<=n;i++)
{
state[i].predecessor=0;
state[i].length=infinity;
state[i].label=tent;
}
state[s].predecessor=0;
state[s].length=0;
state[s].label=perm;
k=s;
do
{
for(i=1;i<=n;i++)
{
if(a[k][i]>0 && state[i].label==tent)
{
if(state[k].length+a[k][i] {
state[i].predecessor=k;
state[i].length=state[k].length+a[k][i];
}
}
}
min=infinity;
k=0;
for(i=1;i<=n;i++)
{
if(state[i].label==tent&&state[i].length {
min=state[i].length;
k=i;
}
}
if(k==0)
return 0;
state[k].label=perm;
}while(k!=t);
k=t;
count=0;
do
{
count++;
rpath[count]=k;
k=state[k].predecessor;
}while(k!=0);
for(i=1;i<=count;i++)
path[i]=rpath[count-i+1];
for(i=1;i *dist+=a[path[i]][path[i+1]];
return count;
}
void main()
{
int a[maxnode][maxnode],i,j;
int path[maxnode];
int from,to,dist,count,n;
clrscr();
printf(“Enter no. of nodes:”);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
{
printf(“Enter node %d”,i);
for(j=1;j<=n;j++)
scanf(“%d”,&a[i][j]);
}
printf(“\n From to”);
scanf(“%d %d”,&from,&to);
count=shortpath(a,n,from,to,path,&dist);
if(dist)
{
printf(“\n Short path”);
printf(“%d”,path[1]);
for(i=2;i<=count;i++)
printf(“–>%d”,path[i]);
printf(“\nMinimum distance is %d \n”,dist);
}
else
printf(“\n Path does not exists”);

getch();
}

OUTPUT

Enter no. of nodes:4
Enter node 1
0 3 4 0
Enter node 2
0 0 6 20
Enter node 3
0 0 0 9
Enter node 4
15 0 0 0

From to 2 4

Short path2–>3–>4
Minimum distance is 15

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow up !

Enter your email address to follow this blog and receive notifications of new posts by email.

iTweet :

Error: Twitter did not respond. Please wait a few minutes and refresh this page.

Where are you?

%d bloggers like this: