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,i,j,min,a,p,st=1,ed=5,stp,edp,t,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

15 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…

2. very efficient code

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

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

5. sivakomaragiri

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

6. sivakomaragiri

Y so??????

7. Azmat saba

this code is not sufficient for the output

8. Need replace  to , because array’s index in C/C++ started from zero instead of 1 like as Pascal

9. SHUBHAM

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

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

11. it actually works…it gives the output

12. Krushna

Can you explain step by step, difficult to understand the program

13. I can enter the cost matrix but it can not ask me to enter the paths

14. I can enter the cost matrix but it can not ask me to enter the paths help me

15. Pratiksha

What do you mean by, “Enter no of paths?”
What paths?

More from C Programs
C Program to convert Prefix Expression into INFIX Research Papers Projects 