Shortest Path example2

#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 s,t,dist,count,n;

char ch;

fflush(stdin);

l:

clrscr();

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

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

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

printf("How many nodes?\n");

scanf("%d",&n);

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

{

printf("Enter node %d connectivity:",i);

printf("\n");

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

if(i==j)

a[i][j]=0;

else

{

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

printf("\n");

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

}

}

printf("\n Enter
the source Node:");

scanf("%d",&s);

printf("\n
Enter the distination Node:");

scanf("%d",&t);

if(s>n
|| t>n || s==t || s<1 || t<1)

{

if(s==t)

{

printf("\nYou Enter the different node for");

printf(" \n source and distination");

}

else

printf("\n
Invalid Input");

}

else

{

count= shortpath(a,n,s,t,path,&dist);

if(dist)

{

printf("\nShortest path:");

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

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

printf("\t%d",path[i]);

printf("\n");

printf("Minimum distance %d",dist);

}

else

{

printf("\nPath does not exist ");

}

printf("\nDo you want continue(Y/N):");

scanf("%s",&ch);

if(ch=='y'||
ch=='Y')

goto l;

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

}