SHORTEST PATH IN GRAPH

#include<stdio.h>

#include<conio.h>

void main()

{

int path[5][5],i,j,min,a[5][5],p,st=1,ed=5,stp,edp,t[5],index;

clrscr();

printf("enter the cost matrix\n");

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

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

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

printf("enter  number of paths\n");

scanf("%d",&p);

printf("enter possible paths\n");

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

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

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

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

{

t[i]=0;

stp=st;

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

{

edp=path[i][j+1];

t[i]=t[i]+a[stp][edp];

if(edp==ed)

break;

else

stp=edp;

}

}

min=t[st];index=st;

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

{

if(min>t[i])

{

min=t[i];

index=i;

}

}

printf("minimum cost %d",min);

printf("\n minimum cost path ");

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

{

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

if(path[index][i]==ed)

break;

}

getch();

}

output:

enter the cost matrix

0 1 4 2 0

0 0 0 2 0

0 0 0 3 0

0 0 0 0 5

0 0 0 0 0

enter  number of paths

4

enter possible paths

1 2 4 5 0

1 2 5 0 0

1 4 5 0 0

1 3 4 5 0

minimum cost 1

 minimum cost path --> 1--> 2--> 5