1  
   2  void dijkstra2(int s) {
   3  	int queue[GRAPHSIZE];
   4  	char inQueue[GRAPHSIZE];
   5  	int begq = 0,
   6  	    endq = 0;
   7  	int i, mini;
   8  	int visited[GRAPHSIZE];
   9  
  10  	for (i = 1; i <= n; ++i) {
  11  		d2[i] = INFINITY;
  12  		visited[i] = 0; /* the i-th element has not yet been visited */
  13  		inQueue[i] = 0;
  14  	}
  15  
  16  	d2[s] = 0;
  17  	queue[endq] = s;
  18  	endq = (endq + 1) % GRAPHSIZE;
  19  
  20  
  21  	while (begq != endq) {
  22  		mini = queue[begq];
  23  		begq = (begq + 1) % GRAPHSIZE;
  24  		inQueue[mini] = 0;
  25  
  26  		visited[mini] = 1;
  27  
  28  		for (i = 1; i <= n; ++i)
  29  			if (dist[mini][i])
  30  				if (d2[mini] + dist[mini][i] < d2[i]) { 
  31  					d2[i] = d2[mini] + dist[mini][i];
  32  					if (!inQueue[i]) {
  33  						queue[endq] = i;
  34  						endq = (endq + 1) % GRAPHSIZE;
  35  						inQueue[i] = 1;
  36  					}
  37  				}
  38  	}
  39  }

   1  
   2  #include <stdio.h>
   3  
   4  #define GRAPHSIZE 2048
   5  #define INFINITY GRAPHSIZE*GRAPHSIZE
   6  #define MAX(a, b) ((a > b) ? (a) : (b))
   7  
   8  int e; /* The number of nonzero edges in the graph */
   9  int n; /* The number of nodes in the graph */
  10  long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
  11  long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
  12  
  13  void printD() {
  14  	int i;
  15  	for (i = 1; i <= n; ++i)
  16  		printf("%10d", i);
  17  	printf("\n");
  18  	for (i = 1; i <= n; ++i) {
  19  		printf("%10ld", d[i]);
  20  	}
  21  	printf("\n");
  22  }
  23  
  24  void dijkstra(int s) {
  25  	int i, k, mini;
  26  	int visited[GRAPHSIZE];
  27  
  28  	for (i = 1; i <= n; ++i) {
  29  		d[i] = INFINITY;
  30  		visited[i] = 0; /* the i-th element has not yet been visited */
  31  	}
  32  
  33  	d[s] = 0;
  34  
  35  	for (k = 1; k <= n; ++k) {
  36  		mini = -1;
  37  		for (i = 1; i <= n; ++i)
  38  			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
  39  				mini = i;
  40  
  41  		visited[mini] = 1;
  42  
  43  		for (i = 1; i <= n; ++i)
  44  			if (dist[mini][i])
  45  				if (d[mini] + dist[mini][i] < d[i]) 
  46  					d[i] = d[mini] + dist[mini][i];
  47  	}
  48  }
  49  
  50  int main(int argc, char *argv[]) {
  51  	int i, j;
  52  	int u, v, w;
  53  
  54  	FILE *fin = fopen("dist.txt", "r");
  55  	fscanf(fin, "%d", &e);
  56  	for (i = 0; i < e; ++i)
  57  		for (j = 0; j < e; ++j)
  58  			dist[i][j] = 0;
  59  	n = -1;
  60  	for (i = 0; i < e; ++i) {
  61  		fscanf(fin, "%d%d%d", &u, &v, &w);
  62  		dist[u][v] = w;
  63  		n = MAX(u, MAX(v, n));
  64  	}
  65  	fclose(fin);
  66  
  67  	dijkstra(1);
  68  
  69  	printD();
  70  
  71  	return 0;
  72  }