C program to find the Shortest path for a given graph

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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

11 Responses to “C program to find the Shortest path for a given graph”

  1. jotheswar

    hi..i found this c code after a long time search…i am doing a project work in shortest path detection… i can’t understand this..can u much detail abt this…its very helpful to me….diagramatic representation of ur eg is much better.plz do this help as soon as possible…

    Reply
  2. The above program is not giving the exact output as it is mentioned above..
    can anyone plz verify it……..?

    Reply
  3. sivakomaragiri

    U r code is executing perfectly in borland c++ compiler and wen done in turboc2 its giving o cost o path…!!

    Reply
  4. Need replace [5][5] to [6][6], because array’s index in C/C++ started from zero instead of 1 like as Pascal

    Reply
  5. SHUBHAM

    i can’t understand this..can u much detail abt this…its very helpful to me….

    Reply
  6. The program is not working,however we change the number of arrays.It’s advisable not to use this coding.

    Reply

Leave a Reply