Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

Speeding Up Dijkstra's Algorithm

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```Demonstrates a way of speeding up the O(n2) 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;
}
}
}
}
``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.