1  
   2  #include <stdio.h>
   3  
   4  int n; /* Then number of nodes */
   5  int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
   6  			it exists, or 0 if it does not */
   7  
   8  void printDist() {
   9  	int i, j;
  10  	printf("    ");
  11  	for (i = 0; i < n; ++i)
  12  		printf("%4c", 'A' + i);
  13  	printf("\n");
  14  	for (i = 0; i < n; ++i) {
  15  		printf("%4c", 'A' + i);
  16  		for (j = 0; j < n; ++j)
  17  			printf("%4d", dist[i][j]);
  18  		printf("\n");
  19  	}
  20  	printf("\n");
  21  }
  22  
  23  /*
  24  	floyd_warshall()
  25  
  26  	after calling this function dist[i][j] will the the minimum distance
  27  	between i and j if it exists (i.e. if there's a path between i and j)
  28  	or 0, otherwise
  29  */
  30  void floyd_warshall() {
  31  	int i, j, k;
  32  	for (k = 0; k < n; ++k) {
  33  		printDist();
  34  		for (i = 0; i < n; ++i)
  35  			for (j = 0; j < n; ++j)
  36  				/* If i and j are different nodes and if 
  37  					the paths between i and k and between
  38  					k and j exist, do */
  39  				if ((dist[i][k] * dist[k][j] != 0) && (i != j))
  40  					/* See if you can't get a shorter path
  41  						between i and j by interspacing
  42  						k somewhere along the current
  43  						path */
  44  					if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
  45  						(dist[i][j] == 0))
  46  						dist[i][j] = dist[i][k] + dist[k][j];
  47  	}
  48  	printDist();
  49  }
  50  
  51  int main(int argc, char *argv[]) {
  52  	FILE *fin = fopen("dist.txt", "r");
  53  	fscanf(fin, "%d", &n);
  54  	int i, j;
  55  	for (i = 0; i < n; ++i)
  56  		for (j = 0; j < n; ++j)
  57  			fscanf(fin, "%d", &dist[i][j]);
  58  	fclose(fin);
  59  
  60  	floyd_warshall();
  61  
  62  	return 0;
  63  }
  64