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  }

   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  }

   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  

   1  
   2  #include <stdio.h>
   3  
   4  /*
   5  	The input file (weight.txt) look something like this
   6  		4
   7  		0 0 0 21
   8  		0 0 8 17
   9  		0 8 0 16
  10  		21 17 16 0
  11  
  12  	The first line contains n, the number of nodes.
  13  	Next is an nxn matrix containg the distances between the nodes
  14  	NOTE: The distance between a node and itself should be 0
  15  */
  16  
  17  int n; /* The number of nodes in the graph */
  18  
  19  int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
  20  			if there is no path between i and j, weight[i][j] should
  21  			be 0 */
  22  
  23  char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
  24  			spanning tree; 0 otherwise*/
  25  
  26  int d[100]; /* d[i] is the distance between node i and the minimum spanning
  27  		tree; this is initially infinity (100000); if i is already in
  28  		the tree, then d[i] is undefined;
  29  		this is just a temporary variable. It's not necessary but speeds
  30  		up execution considerably (by a factor of n) */
  31  
  32  int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be
  33  			linked to in order to get a distance of d[i] */
  34  
  35  /* updateDistances(int target)
  36  	should be called immediately after target is added to the tree;
  37  	updates d so that the values are correct (goes through target's
  38  	neighbours making sure that the distances between them and the tree
  39  	are indeed minimum)
  40  */
  41  void updateDistances(int target) {
  42  	int i;
  43  	for (i = 0; i < n; ++i)
  44  		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {
  45  			d[i] = weight[target][i];
  46  			whoTo[i] = target;
  47  		}
  48  }
  49  
  50  int main(int argc, char *argv[]) {
  51  	FILE *f = fopen("dist.txt", "r");
  52  	fscanf(f, "%d", &n);
  53  	int i, j;
  54  	for (i = 0; i < n; ++i)
  55  		for (j = 0; j < n; ++j)
  56  			fscanf(f, "%d", &weight[i][j]);
  57  	fclose(f);
  58  
  59  	/* Initialise d with infinity */
  60  	for (i = 0; i < n; ++i)
  61  		d[i] = 100000;
  62  
  63  	/* Mark all nodes as NOT beeing in the minimum spanning tree */
  64  	for (i = 0; i < n; ++i)
  65  		inTree[i] = 0;
  66  
  67  	/* Add the first node to the tree */
  68  	printf("Adding node %c\n", 0 + 'A');
  69  	inTree[0] = 1;
  70  	updateDistances(0);
  71  
  72  	int total = 0;
  73  	int treeSize;
  74  	for (treeSize = 1; treeSize < n; ++treeSize) {
  75  		/* Find the node with the smallest distance to the tree */
  76  		int min = -1;
  77  		for (i = 0; i < n; ++i)
  78  			if (!inTree[i])
  79  				if ((min == -1) || (d[min] > d[i]))
  80  					min = i;
  81  
  82  		/* And add it */
  83  		printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
  84  		inTree[min] = 1;
  85  		total += d[min];
  86  
  87  		updateDistances(min);
  88  	}
  89  
  90  	printf("Total distance: %d\n", total);
  91  
  92  	return 0;
  93  }
  94