Speeding Up Dijkstra's Algorithm

• Tweet
• 

        Demonstrates a way of speeding up the O(n<sup>2</sup>) 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 <a href="http://compprog.wordpress.com/2008/01/17/speeding-up-dijkstras-algorithm-1/">this</a>.

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;
					}
				}
	}
}

Tags:
• algorithm
• C
• dijkstra
• graph
• graphs
• speeding
• Up