#include <stdio.h>

#define MAX 100    // maximum number of vertices
#define INF 10000  // must be bigger than any shortest-path

double graph[MAX][MAX];

void init_graph(int size) {
  int i, j;
  for (i=0; i<size; i++)
    for (j=0; j<size;j++)
      graph[i][j] = i==j ? 0 : INF;
}

void warshall(int size) {
  register int i, j, k;
  for (k=size-1; k>=0; k--)
    for (i=size-1; i>=0; i--)
      for (j=size-1; j>=0; j--) {
        double dist = graph[i][k] + graph[k][j];
        if (dist < graph[i][j]) graph[i][j] = dist;
      }
}

void print_graph(int size) {
  int i, j;
  for (i=0; i<size; i++) {
    for (j=0; j<size; j++)
      printf("%5d  ", (int)graph[i][j]);
    putchar('\n');
  }
}

int main() {
  init_graph(5);

  // ... make up a graph (from CLR p. 556)
  graph[0][1] = 3;
  graph[0][2] = 8;
  graph[0][4] = -4;
  graph[1][3] = 1;
  graph[1][4] = 7;
  graph[2][1] = 4;
  graph[3][0] = 2;
  graph[3][2] = -5;
  graph[4][3] = 6;
  warshall(5);
  print_graph(5);
  return 0;
}