SINGLE SOURCE SHORTEST PATH PROBLEM(DIJKSTRA'S ALGORITHM) 'C' PROGRAM

1. #include<stdio.h>
2. #include<limits.h>
3. int n;
4. int adj[10][10],vi[10];
5. int dist[10];
6. void shortest(int v);
7. int min();
8. int main(){
9. int i,j,s;
10. printf("enter number of vertices\n");
11. scanf("%d",&n);
12. for(i=1;i<=n;i++){
13. dist[i]=INT_MAX;
14. printf("%d\t",dist[i]);
15. }
16. printf("enter adjacency matrix\n");
17. for(i=1;i<=n;i++)
18. for(j=1;j<=n;j++)
19. scanf("%d",&adj[i][j]);
20. printf("enter source vertex to start\n");
21. scanf("%d",&s);
22. shortest(s);
23. printf("shortest distances from vertex %d are\n",s);
24. for(i=1;i<=n;i++){
25. if(dist[i]<INT_MAX&&vi[i]==1)
26. printf("cost:%d\tedge:(%d,%d)\n",dist[i],s,i);
27. }
28. return 0;
29. }
30.  void shortest(int v){
31. int i,j,u;
32. for(i=1;i<=n;i++){
33. vi[i]=-1;
34. if(adj[v][i]!=0)
35. dist[i]=adj[v][i];
36. }
37. vi[v]=1;
38. for(j=2;j<=n;j++){
39. u=min();
40. printf("%d\n",u);
41. vi[u]=1;
42. for(i=1;i<=n;i++){
43. if((adj[u][i]!=0)&&(dist[i]>(dist[u]+adj[u][i]))&&(vi[i]==-1)){
44. dist[i]=(dist[u]+adj[u][i]);
45. }
46. }
47. }
48. return;
49. }
50. int min(){
51.  int i,t=dist[1],j;
52. for(i=1;i<=n;i++){
53. if((dist[i]<t)&&(vi[i]==-1))
54. {
55. t=dist[i];
56. }}
57. for(j=1;j<=n;j++){
58. if(t==dist[j]&&vi[j]==-1)
59. break;}
60. return j;
61. }