electrofriends.com > Source Codes > Software Programs > C Programs > C program to find the Shortest path for a given graph

C program to find the Shortest path for a given graph

Sunday, September 20th, 2009

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

Avatar of Ranjith

Author Name :
Ranjith

Total : 6 Comments

Simillar Posts

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

  1. jotheswar says:
    September 30, 2009 at 4:55 pm

    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…

  2. karthik says:
    January 18, 2011 at 3:19 pm

    very efficient code

  3. kutti says:
    February 22, 2012 at 2:59 pm

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

  4. niks says:
    July 9, 2012 at 2:23 pm

    can u give me a method to generate the possible paths ??

  5. sivakomaragiri says:
    October 30, 2012 at 1:35 pm

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

  6. sivakomaragiri says:
    October 30, 2012 at 1:36 pm

    Y so??????

Leave a Reply

Question and Answer
C/C++ Unix & Linux Wordpress
Source codes
C C++ Java

Free email signup

Email: