Dijkstra's algorithm with priority queue

Question

In my implementation of Dijkstra's algorithm I have 1 array with all nodes and 1 priority queue with all nodes. Whenever a node is dequeued I update all adjacent nodes with new distance and where it came from, so I can backtrack the path.

The node in the priority queue is updated with new distance and the node in the array is updated where it came from and with new distance. When a node is dequeued the final distance in the array is updated:

  PathInfo current = pq.remove();
  path[current.pos].distance = current.distance;

Is it acceptable to update both the array with info about previous node and the priority queue with distance?

This happens whenever a better distance is found:

      PathInfo key(i, newDistance);
      path[i].distance = newDistance;
      path[i].previous = current.pos;
      pq.decreaseKey(key);

It seems a bit redundant to update my array and priority queue with basically the same info.

I'm currently using a regular array as a data structure in the PQ. Updating the priority is done in linear time and dequeueing is also done in linear time.

What data structure should I use in the priority queue and how should I change a nodes priority?

I'm using C++

Answer 1

You have two kinds of distances here: your priority queue has "tentative distances" which are subject to update, while your array has "final distances", which are not (because Dijkstra's algorithm doesn't need to update nodes that have been removed from the priority queue).

It appears that you are unnecessarily updating the distances in your array. Perhaps it would also be a good idea to change the field name in your array node to document this: from arrayNode.distance to arrayNode.finalDistance.

In other words: it appears you are using your array nodes to output the results from your Dijkstra's algorithm -- so you should only set the distance in each array node once, when it is removed from the priority queue.

---

If your priority-queue implementation doesn't provide the ability to query the current distance associated with a given key, please check the behavior of its decreaseKey() operation. If the decreaseKey() operation rejects updates for which the new priority does not actually decrease, then you shouldn't need to perform that check yourself -- you can just call it for each neighbor of the current node.

However, if the decreaseKey() function does not handle that case correctly, and there is no auxiliary query function that would let you perform that check manually, and there is no opportunity to fix either deficiency, then you'll need to maintain redundant information for that purpose....