Why priority Queue is used in Djisktra's Algorithm
HardThe heap hands you the nearest node instantly
Problem
Understand why Dijkstra uses a min-priority-queue: to always pick the currently closest node efficiently.
The heap hands you the nearest unfinished node instantly instead of scanning them all.
The idea
Dijkstra repeatedly needs the closest unfinished node. Scanning an array for it costs O(V) each time, so the whole run is O(V²). A min-heap (priority queue) returns that minimum in O(log V), dropping the total to O(E log V). Watch the 'frontier' readout below: the heap always surfaces its smallest entry for free — that is the node Dijkstra settles next.
Step 1 of 13. Goal: the shortest distance from A to every other node. Start A = 0, everyone else = ∞ (unknown). dist [0, ∞, ∞, ∞, ∞], settled —.
1dist[src] = 0, all others = ∞2min-heap H = {(0, src)}3while H not empty:4 (d, u) = pop-smallest from H // O(log V), not an O(V) scan5 for each edge (u → v, weight w):6 if d + w < dist[v]:7 dist[v] = d + w; push (dist[v], v)8return distInput
- nodes
- 5, 6 edges
Memory
- dist
- [0, ∞, ∞, ∞, ∞]
- frontier
- —
Output
- settled
- —
- shortest dist
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- compare with linear scan
- Output:
- heap is faster
Finished the walkthrough? Add it to your streak.