Shortest Path

#include<stdio.h>

#include<conio.h>

#include<limits.h>

#define MAXNODE 10

#define

PERM
1

#define TENT 2

#define infinity INT_MAX

typedef
struct NODELABEL

{

int predecessor;

int length;

int label;

}NODELABEL;

main()

{

int a[MAXNODE][MAXNODE],i,j;

int path[MAXNODE];

int from,to,dist,count,n;

fflush(stdin);

clrscr();

printf("\n\t\t\t SHORTEST PATH ");

printf("\n\t\t\t **************\n");

A:

printf("\nEnter the Number of nodes(n>2):
");

scanf("%d",&n);

if(n<=2)

goto A;

for(i=1;i<=n;i++)

{

printf("\n");

for(j=1;j<=n;j++)

if(i==j)

a[i][j]=0;

else

{

printf("%d->%d Distance :",
i,j);

scanf("%d",&a[i][j]);

}

}

l:

printf("\n\nEnter the source:");

scanf("%d",&from);

printf("\nEnter the Destination:");

scanf("%d",&to);

if((from>n)||(to>n)||(from<1)||(to<1))

{

printf("\nPath does not exist");

goto l;

}

count=shortpath(a,n,from,to,path,&dist);

if(dist)

{ printf("\nShortest path for %d-->%d is :",from,to);

printf("%d",path[1]);

for(i=2;i<=count;i++)

printf("-->%d",path[i]);

printf("\tMinimum distance = %d",dist);

}

else

printf("\nsource and destination are same");

getch();

}

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;

int 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].length)

{

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)

{

min=state[i].length;

k=i;

} }

if(k==0)

return(0);

state[k].label=PERM;

}while(k!=t);

k=t;

count=0;

do
{

count=count+1;

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<count;i++)

*dist+=a[path[i]][path[i+1]];

return(count);

}