Dijkstra's algorithm and priority queue

In Dijkstra's algorithm, there are two operations:

1. return and remove the node with the shortest distance from the queue;
2. insert a new node into the queue or updated the distance of a node that is already in the queue.

Priority queue is the standard data structure for these operations. The time complexity of Dijkstra's algorithm is determined by the implementation of the priority queue. Priority queue can be implemented as heap, binary search tree and even, linked list if you do not care about the algorithm efficiency.

In my C++ code, std::set serves as a priority queue and it is usually implemented as balanced binary search tree in STL. std:set::begin() returns the node with the shortest distance from the origin. Q.erase(Q.find(node(cost[i],i))) removes node i if it's in the queue. Then the updated distance is inserted by Q.insert(node(cost[i],i)). Actually, C++ STL provides std::priority_queue. However, it does not allow to update distance (the second operation).

The Python standard library does not provide any binary search tree, like std::set(). It only has a heap queue module, heapq, which does not support distance updating either. One option is to implement a heap that supports updating operation. If you follow this approach, you may find IndexMinPQ.java useful.

But a much simpler approach is to change the algorithm a little bit and make use of heapq. We can just allow multiple elements in the queue associated with the same node in the graph. During edge relaxation, any node with updated distance is inserted into the queue, no matter if it's in the queue or not. Then when a node is popped out of the queue, if it is the first time that it is popped out, relax all the edge linked with this node; otherwise, ignore it and pop out another node from the queue. The modified python code is based on this idea. The time complexity of the modified algorithm is O(E logE), which is a bit slower than the standard Dijkstra's algorithm. Here is a python implementation of the modified Dijkstra's algorithm.