Step through Dijkstra's algorithm node by node. Watch the priority queue drive exploration and distances lock in, closest first.
Graphs · Classic Algorithm · Greedy + Min-Heap
Given a weighted, undirected graph with non-negative edge weights and a source node S,
find the shortest distance from S to every other node.
Greedy insight: always process the closest unvisited node next.
Once a node is extracted from the min-heap, its distance is final — no shorter
path can exist, because all remaining paths pass through nodes that are at least as far away.
Greedy Guarantee
When node u is popped with distance d, every node remaining in the
queue has distance ≥ d. Any alternative path to u would route through one of those nodes,
making its total length ≥ d. So d is already optimal.
Core Invariant
When a node is popped from the min-heap, its distance is the true shortest path. It will never be updated again — this is the key property that makes Dijkstra's correct and efficient.
Edge Relaxation
if dist[u] + w(u,v) < dist[v]:
dist[v] = dist[u] + w(u,v)
prev[v] = u
Initialize: dist[S] = 0, all others = ∞. Add S to the priority queue.
Once extracted from the min-heap with distance d, a node's distance is proven optimal — any alternative path would go through an unvisited node v where dist[v] ≥ d, making it at least as long.
Time
O((V + E) log V) with a binary heap
Space
O(V) for dist[] and prev[] arrays
Pattern
Greedy + Min-Heap (Priority Queue)
Constraint
Edge weights must be non-negative. Use Bellman-Ford for negative weights.