# 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

### 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. sivakomaragiri

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

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

6. SHUBHAM

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

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

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