Speeding up Dijkstra's Algorithm

scvalex (Alexandru Scvortov) — Thu, 17 Jan 2008 15:57:42 GMT

Demonstrates a way of speeding up the O(n²) version of Dijkstra's Algorithm by about 4x.

Here, dist[][] is the adjacency matrix representing the graph and n is the number of nodes. d2[] is where the lengths of the shortest paths are saved.

For a full explanation, see this.



void dijkstra2(int s) {

	int queue[GRAPHSIZE];

	char inQueue[GRAPHSIZE];

	int begq = 0,

	    endq = 0;

	int i, mini;

	int visited[GRAPHSIZE];



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

		d2[i] = INFINITY;

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

		inQueue[i] = 0;

	}



	d2[s] = 0;

	queue[endq] = s;

	endq = (endq + 1) % GRAPHSIZE;





	while (begq != endq) {

		mini = queue[begq];

		begq = (begq + 1) % GRAPHSIZE;

		inQueue[mini] = 0;



		visited[mini] = 1;



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

			if (dist[mini][i])

				if (d2[mini] + dist[mini][i] < d2[i]) { 

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

					if (!inQueue[i]) {

						queue[endq] = i;

						endq = (endq + 1) % GRAPHSIZE;

						inQueue[i] = 1;

					}

				}

	}

}

DZone Snippets: speeding code

Speeding up Dijkstra's Algorithm