#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 3
 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 : 4
 minimum cost path :
 1–>2–>5

• Pin It
• Share
• Tweet

Be Sociable, Share!

• 

Related posts:

1. C++ program – Solve the single source shortest path problem Using Dijkstra’s algorithm
2. C++ program – Implement dynamic programming algorithm to solve the all pairs shortest path problem
3. C program to accept a figure code and find the ares of different geometrical figures such as circle, square, rectangle etc using switch
4. C program – Shortest Job Next
5. C program to read two matrices A (MxN) and B(MxN) and perform addition OR subtraction of A and B. Find the trace of the resultant matrix. Output the given matrix, their sum or Differences and the trace.

Tagged as: C program to find the Shortest path for a given graph, find the Shortest path for a given graph, the Shortest path for a given graph