/******************************************************************************
 *
 * path.c                                                   Wolfgang Schreiner
 * all pairs shortest path problem
 *
 * In:  N x N matrix W such that
 *      W(i,j) = weight of edge from i to j (or infinity, if none)
 *
 * Out: N x N matrix W such that
 *      W(i,j) = length of shortest path from i to j (or infinity, if none)
 *
 *****************************************************************************/

#include <stdio.h>          /* input/output */
#include <stdlib.h>         /* random generator, minimum function */

#define N   256             /* matrix dimension */
#define L   8               /* N = 2^L */
#define D   1               /* matrix density in percent */
#define MAX 100             /* maximum edge weight */
#define INF N*MAX+1         /* infinity, N*MAX < INF, 2*INF must be in range */

#define RANDOM() rand()     /* random generator, sometimes called random() */
#define MIN(a,b) ((a) <= (b) ? (a) : (b))

typedef int   INDEX;        /* indices */
typedef int   COUNTER;      /* counters */
typedef float ELEM;         /* matrix elements */
typedef ELEM  MATRIX[N][N]; /* matrix */

int flag = 0;               /* print result flag */

/******************************************************************************
 * initialize W
 *****************************************************************************/
void init(MATRIX W) {

  INDEX i, j;

  for (i = 0; i < N; i++) {        /* initialize by random numbers */
    for (j = 0; j < N; j++) {
      if (RANDOM() % (100/D) == 0)
	W[i][j] = RANDOM() % MAX;  /* weight of edge between i and j */
      else
	W[i][j] = INF;             /* no edge between i and j */
    }
  }
  for (i = 0; i < N; i++)          /* initialize diagonale */
    W[i][i] = 0;

}

/******************************************************************************
 * print W
 *****************************************************************************/
void print(MATRIX W) {

  INDEX i, j;
  COUNTER n;

  n = 0;
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      if (W[i][j] == INF) {
	if (flag) printf(" ");
      }
      else {
	n++;
        if (flag) printf(".");
      }
    }
    if (flag) printf("\n");
  }
  printf("*** %d paths ***\n", n);

}

/******************************************************************************
 * square matrix A yielding B using MIN and + instead of + and *
 *****************************************************************************/
void square(MATRIX A, MATRIX B) {

  INDEX i, j, k;
  ELEM m;

  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      m = A[i][j];
      for (k = 0; k < N; k++) {
        m = MIN(m, A[i][k] + A[k][j]);
      }
      B[i][j] = m;
    }
  }

}

/******************************************************************************
 * copy A to B
 *****************************************************************************/
void copy(MATRIX A, MATRIX B) {

  INDEX i, j;

  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      B[i][j] = A[i][j];            
    }
  }

}

/******************************************************************************
 * compute all pairs shortest paths
 *****************************************************************************/
void path(MATRIX W) {

  COUNTER s, t;
  MATRIX V;

  t = 0;
  for (s = 0; s < L ; s++) {   
    if (t == 0)
      square(W, V);             /* V = W^2 */
    else
      square(V, W);             /* W = V^2 */
    t = 1 - t;
  }
  if (t == 1) copy(V, W);       /* W = V */

}

/******************************************************************************
 * main program
 *****************************************************************************/
int main(int argc, int *argv[]) {

  MATRIX W;

  init(W);  /* initialize matrix */
  print(W); /* print input */
  path(W);  /* compute all shortest pathes */
  print(W); /* print result */

  return(0);

}

/******************************************************************************
 * end of path.c
 *****************************************************************************/