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;

void main()

{

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

int path[MAXNODE];

int from,to,dist,count,n;

fflush(stdin);

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

{

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

printf("\n");

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

}

}

printf("From to where? \n");

scanf("%d
%d", &from, &to);

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

if(dist)

{

printf("Shortest path \n");

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

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

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

printf("\nMinimum distance %d",dist);

}

else

printf("Path does not exist");

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

}