Return to Answer

###Optimization###

Your dijkstra implementation can potentially push the same vertex onto the priority queue more than once. This happens when you encounter a vertex for the second time, but this time its distance is less than its previous distance. Because of this, you may find yourself pulling the same vertex off the priority queue multiple times. You should add the following check in the outer loop:

candidates.pop();
if (visited[next])
    continue;

otherwise your algorithm may run far slower than it should.

###Bug###

I didn't notice this before, but your loop termination condition is wrong. You are looping exactly n-1 times under the assumption that each loop adds a vertex to the path. However, due to the duplicate vertex possibility mentioned above, you may not make progress on each loop iteration. You should modify the loop to terminate when the priority queue becomes empty. Alternatively, you can keep a count of the number of visited vertices and terminate when you reach n.

Optimization

Your dijkstra implementation can potentially push the same vertex onto the priority queue more than once. This happens when you encounter a vertex for the second time, but this time its distance is less than its previous distance. Because of this, you may find yourself pulling the same vertex off the priority queue multiple times. You should add the following check in the outer loop:

candidates.pop();
if (visited[next])
    continue;

otherwise your algorithm may run far slower than it should.

Bug

I didn't notice this before, but your loop termination condition is wrong. You are looping exactly n-1 times under the assumption that each loop adds a vertex to the path. However, due to the duplicate vertex possibility mentioned above, you may not make progress on each loop iteration. You should modify the loop to terminate when the priority queue becomes empty. Alternatively, you can keep a count of the number of visited vertices and terminate when you reach n.

###Optimization###

Your dijkstra implementation can potentially push the same vertex onto the priority queue more than once. This happens when you encounter a vertex for the second time, but this time its distance is less than its previous distance. Because of this, you may find yourself pulling the same vertex off the priority queue multiple times. You should add the following check:

if (visited[next])
    continue;

otherwise your algorithm may run far slower than it should.

###Bug###

I didn't notice this before, but your loop termination condition is wrong. You are looping exactly n-1 times under the assumption that each loop adds a vertex to the path. However, due to the duplicate vertex possibility mentioned above, you may not make progress on each loop iteration. You should modify the loop to terminate when the priority queue becomes empty. Alternatively, you can keep a count of the number of visited vertices and terminate when you reach n.

###Optimization###

Your dijkstra implementation can potentially push the same vertex onto the priority queue more than once. This happens when you encounter a vertex for the second time, but this time its distance is less than its previous distance. Because of this, you may find yourself pulling the same vertex off the priority queue multiple times. You should add the following check in the outer loop:

candidates.pop();
if (visited[next])
    continue;

otherwise your algorithm may run far slower than it should.

###Bug###

I didn't notice this before, but your loop termination condition is wrong. You are looping exactly n-1 times under the assumption that each loop adds a vertex to the path. However, due to the duplicate vertex possibility mentioned above, you may not make progress on each loop iteration. You should modify the loop to terminate when the priority queue becomes empty. Alternatively, you can keep a count of the number of visited vertices and terminate when you reach n.

###Optimization###

Your dijkstra implementation can potentially push the same vertex onto the priority queue more than once. This happens when you encounter a vertex for the second time, but this time its distance is less than its previous distance. Because of this, you may find yourself pulling the same vertex off the priority queue multiple times. You should add the following check:

if (visited[next])
    continue;

otherwise your algorithm may run far slower than it should.

###Optimization###

Your dijkstra implementation can potentially push the same vertex onto the priority queue more than once. This happens when you encounter a vertex for the second time, but this time its distance is less than its previous distance. Because of this, you may find yourself pulling the same vertex off the priority queue multiple times. You should add the following check:

if (visited[next])
    continue;

otherwise your algorithm may run far slower than it should.

###Bug###

I didn't notice this before, but your loop termination condition is wrong. You are looping exactly n-1 times under the assumption that each loop adds a vertex to the path. However, due to the duplicate vertex possibility mentioned above, you may not make progress on each loop iteration. You should modify the loop to terminate when the priority queue becomes empty. Alternatively, you can keep a count of the number of visited vertices and terminate when you reach n.