Instead of using a normal Queue, we use a PriorityQueue.
Priority queues need to know what “priority” means for the underlying min–heap to do its thing.
So we use the current $\ce{dist}[v]$ as the priority/key for a vertex $v$.
As we relax more edges, we update the priority for $v$ using a small helper function:
function UpdatePriority(v: Vertex, new_priority: number)
The priority queue will do the update in $O(\log n)$ time if using heaps.
function Dijkstra_NonNegative(G, start):
InitSSSP(G, start)
dist[start] = 0
queue = PriorityQueue()
for each vertex v in G:
put v in queue with priority dist[v]
while queue is not empty:
u = queue.ExtractMin()
for each adjacent vertex v:
if dist[v] > dist[u] + weight(u→v):
dist[v] = dist[u] + weight(u→v)
pred[v] = u
queue.UpdatePriority(v, dist[v])
Complexity
O(V log V)
O(E) with inner for
O(log V) for heaps
already counted
O(log V) for heaps
Dijkstra’s will try to visit every edge, so the while and for together runs $E$ times.
UpdatePriority() , Insert(), ExtractMin() are all $O(\log n)$ if we are using heaps.
They are all priority queue methods and the queue will have at most $V$ vertices, so $O(\log V)$.
Together the algorithm runs in $O(E\log V)$ time.
More Details Including using an array instead of heaps