DZone Snippets: shortest path code

Dijkstra's Algorithm

scvalex (Alexandru Scvortov) — Sat, 01 Dec 2007 19:41:53 GMT

This is a simple O(n^2) implementation of Dijkstra's algorithm for finding the shortest paths from a single source to all nodes in a graph.

Further explanation is given here.



#include 



#define GRAPHSIZE 2048

#define INFINITY GRAPHSIZE*GRAPHSIZE

#define MAX(a, b) ((a > b) ? (a) : (b))



int e; /* The number of nonzero edges in the graph */

int n; /* The number of nodes in the graph */

long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */

long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */



void printD() {

	int i;

	for (i = 1; i <= n; ++i)

		printf("%10d", i);

	printf("\n");

	for (i = 1; i <= n; ++i) {

		printf("%10ld", d[i]);

	}

	printf("\n");

}



void dijkstra(int s) {

	int i, k, mini;

	int visited[GRAPHSIZE];



	for (i = 1; i <= n; ++i) {

		d[i] = INFINITY;

		visited[i] = 0; /* the i-th element has not yet been visited */

	}



	d[s] = 0;



	for (k = 1; k <= n; ++k) {

		mini = -1;

		for (i = 1; i <= n; ++i)

			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))

				mini = i;



		visited[mini] = 1;



		for (i = 1; i <= n; ++i)

			if (dist[mini][i])

				if (d[mini] + dist[mini][i] < d[i]) 

					d[i] = d[mini] + dist[mini][i];

	}

}



int main(int argc, char *argv[]) {

	int i, j;

	int u, v, w;



	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &e);

	for (i = 0; i < e; ++i)

		for (j = 0; j < e; ++j)

			dist[i][j] = 0;

	n = -1;

	for (i = 0; i < e; ++i) {

		fscanf(fin, "%d%d%d", &u, &v, &w);

		dist[u][v] = w;

		n = MAX(u, MAX(v, n));

	}

	fclose(fin);



	dijkstra(1);



	printD();



	return 0;

}

All Sources Shortest Path: The Floyd-Warshall Algorithm

scvalex (Alexandru Scvortov) — Thu, 15 Nov 2007 16:19:25 GMT

This is a straightforward implementation of the Floyd-Warshall algorithm for finding the shortest path between all nodes of a graph.

A more detailed explanation is given here.



#include 



int n; /* Then number of nodes */

int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if

			it exists, or 0 if it does not */



void printDist() {

	int i, j;

	printf("    ");

	for (i = 0; i < n; ++i)

		printf("%4c", 'A' + i);

	printf("\n");

	for (i = 0; i < n; ++i) {

		printf("%4c", 'A' + i);

		for (j = 0; j < n; ++j)

			printf("%4d", dist[i][j]);

		printf("\n");

	}

	printf("\n");

}



/*

	floyd_warshall()



	after calling this function dist[i][j] will the the minimum distance

	between i and j if it exists (i.e. if there's a path between i and j)

	or 0, otherwise

*/

void floyd_warshall() {

	int i, j, k;

	for (k = 0; k < n; ++k) {

		printDist();

		for (i = 0; i < n; ++i)

			for (j = 0; j < n; ++j)

				/* If i and j are different nodes and if 

					the paths between i and k and between

					k and j exist, do */

				if ((dist[i][k] * dist[k][j] != 0) && (i != j))

					/* See if you can't get a shorter path

						between i and j by interspacing

						k somewhere along the current

						path */

					if ((dist[i][k] + dist[k][j] < dist[i][j]) ||

						(dist[i][j] == 0))

						dist[i][j] = dist[i][k] + dist[k][j];

	}

	printDist();

}



int main(int argc, char *argv[]) {

	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &n);

	int i, j;

	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j)

			fscanf(fin, "%d", &dist[i][j]);

	fclose(fin);



	floyd_warshall();



	return 0;

}