Dijkstra's Algorithm with a Priority Queue

Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights. It works by greedily processing nodes in order of their current best-known distance — always expanding the nearest unvisited node. The key data structure is a min-heap (priority queue) that efficiently retrieves the node with the smallest distance.

Dijkstra's algorithm: (1) Initialise dist[source] = 0 and dist[all others] = inf. (2) Push (0, source) onto a min-heap. (3) Pop the node u with smallest distance. If it has already been visited with a smaller distance, skip it. (4) For each neighbour v of u: if dist[u] + weight(u,v) < dist[v], update dist[v] and push (dist[v], v) to the heap. (5) Repeat until heap is empty.