all pair shortest path algorithm in c with program

1/* ALL PAIR SHORTEST PATH */
2
3#include<stdlib.h>
4#include<stdio.h>
5#include<conio.h>
6
7int c[100][100], p[100][100];  //c-cost matrix, p-path matrix(to store the path)
8int inf=1000, v;     //Assume Infinity as 1000
9//int min(int x, int y);
10void show();
11void path(int, int);
12
13int main()
14{
15 int i, j, k, x;
16 clrscr();
17
18 printf("Enter the number of vertices in the graph: ");
19 scanf("%d", &v);
20
21/*
22 for(i=1;i<=v;i++)
23  for(j=1;j<=v;j++)
24   if(i==j)
25    c[i][j]=0;
26   else
27   {
28    printf("Is %d connected to %d?",i,j);
29    printf("If yes, enter weight, else enter %d: ",inf);
30    scanf("%d", &c[i][j]);
31   }
32*/
33
34 printf("\nEnter adjacency matrix:\n");
35 printf("(Enter 1000 if there is no path)\n");
36 for(i=1;i<=v;i++)
37  for(j=1;j<=v;j++)
38  {
39   scanf("%d", &c[i][j]);
40   p[i][j]=-1;
41  }
42
43 printf("\n");
44
45 for(k=1;k<=v;k++)
46 {
47  for(i=1;i<=v;i++)
48  {
49   for(j=1;j<=v;j++)
50   {
51    if(i==j)
52     c[i][j]=0;
53    else
54    {
55     x=c[i][k]+c[k][j];
56     if(c[i][j]>x)
57     {
58      c[i][j]=x;
59      p[i][j]=k;
60     }
61    }
62   }
63  }
64  show();
65  printf("\n");
66 }
67
68 printf("From\tTo\tPath\t\tTotal Min. Cost\n");
69 for(i=1;i<=v;i++)
70 {
71  for(j=1;j<=v;j++)
72  {
73   if(i!=j)
74   {
75    printf("%d\t", i);
76    printf("%d\t", j);
77
78//    printf("Path from %d to %d is: ",i,j);
79    printf("%d", i);
80    path(i,j);
81    printf("%d", j);
82
83    printf("\t\t%d", c[i][j]);
84    printf("\n");
85   }
86  }
87 }
88 getch();
89 return 0;
90}
91
92//-------TO SHOW THE PASSES-------
93void show()
94{
95 int i,j;
96 for(i=1;i<=v;i++)
97 {
98  for(j=1;j<=v;j++)
99   if(c[i][j]==1000)
100    printf("INF\t");
101   else
102    printf("%d\t", c[i][j]);
103  printf("\n");
104 }
105}
106
107//-------TO SHOW THE PATH-------
108void path(int i, int j)
109{
110 int k;
111
112 k=p[i][j];
113 if(k==-1)
114 {
115  printf("->");
116  return;
117 }
118 path(i, k);
119 printf("%d",k);
120 path(k,j);
121}
122
123/* OUTPUT
124
125Enter the number of vertices in the graph: 3
126
127Enter adjacency matrix:
128(Enter 1000 if there is no path)
1290 8 5
1303 0 1000
1311000 2 0
132
1330       8       5
1343       0       8
135INF     2       0
136
1370       8       5
1383       0       8
1395       2       0
140
1410       7       5
1423       0       8
1435       2       0
144
145From    To      Path            Total Min. Cost
1461       2       1->3->2         7
1471       3       1->3            5
1482       1       2->1            3
1492       3       2->1->3         8
1503       1       3->2->1         5
1513       2       3->2            2
152*/
153