1: #include <stdio.h>
    2: 
    3: #define MAX 100    // maximum number of vertices
    4: #define INF 10000  // must be bigger than any shortest-path
    5: 
    6: double graph[MAX][MAX];
    7: 
    8: void init_graph(int size) {
    9:   int i, j;
   10:   for (i=0; i<size; i++)
   11:     for (j=0; j<size;j++)
   12:       graph[i][j] = i==j ? 0 : INF;
   13: }
   14: 
   15: void warshall(int size) {
   16:   register int i, j, k;
   17:   for (k=size-1; k>=0; k--)
   18:     for (i=size-1; i>=0; i--)
   19:       for (j=size-1; j>=0; j--) {
   20:         double dist = graph[i][k] + graph[k][j];
   21:         if (dist < graph[i][j]) graph[i][j] = dist;
   22:       }
   23: }
   24: 
   25: void print_graph(int size) {
   26:   int i, j;
   27:   for (i=0; i<size; i++) {
   28:     for (j=0; j<size; j++)
   29:       printf("%5d  ", (int)graph[i][j]);
   30:     putchar('\n');
   31:   }
   32: }
   33: 
   34: int main() {
   35:   init_graph(5);
   36: 
   37:   // ... make up a graph (from CLR p. 556)
   38:   graph[0][1] = 3;
   39:   graph[0][2] = 8;
   40:   graph[0][4] = -4;
   41:   graph[1][3] = 1;
   42:   graph[1][4] = 7;
   43:   graph[2][1] = 4;
   44:   graph[3][0] = 2;
   45:   graph[3][2] = -5;
   46:   graph[4][3] = 6;
   47:   warshall(5);
   48:   print_graph(5);
   49:   return 0;
   50: }