1  
   2  #include <stdio.h>
   3  
   4  typedef struct {
   5  	int u, v, w;
   6  } Edge;
   7  
   8  int n; /* the number of nodes */
   9  int e; /* the number of edges */
  10  Edge edges[1024]; /* large enough for n <= 2^5=32 */
  11  int d[32]; /* d[i] is the minimum distance from node s to node i */
  12  
  13  #define INFINITY 10000
  14  
  15  void printDist() {
  16  	int i;
  17  
  18  	printf("Distances:\n");
  19  
  20  	for (i = 0; i < n; ++i)
  21  		printf("to %d\t", i + 1);
  22  	printf("\n");
  23  
  24  	for (i = 0; i < n; ++i)
  25  		printf("%d\t", d[i]);
  26  
  27  	printf("\n\n");
  28  }
  29  
  30  void bellman_ford(int s) {
  31  	int i, j;
  32  
  33  	for (i = 0; i < n; ++i)
  34  		d[i] = INFINITY;
  35  
  36  	d[s] = 0;
  37  
  38  	for (i = 0; i < n - 1; ++i)
  39  		for (j = 0; j < e; ++j)
  40  			if (d[edges[j].u] + edges[j].w < d[edges[j].v])
  41  				d[edges[j].v] = d[edges[j].u] + edges[j].w;
  42  }
  43  
  44  int main(int argc, char *argv[]) {
  45  	int i, j;
  46  	int w;
  47  
  48  	FILE *fin = fopen("dist.txt", "r");
  49  	fscanf(fin, "%d", &n);
  50  	e = 0;
  51  
  52  	for (i = 0; i < n; ++i)
  53  		for (j = 0; j < n; ++j) {
  54  			fscanf(fin, "%d", &w);
  55  			if (w != 0) {
  56  				edges[e].u = i;
  57  				edges[e].v = j;
  58  				edges[e].w = w;
  59  				++e;
  60  			}
  61  		}
  62  	fclose(fin);
  63  
  64  	/* printDist(); */
  65  
  66  	bellman_ford(0);
  67  
  68  	printDist();
  69  
  70  	return 0;
  71  }