The greedy idea
Dijkstra finds the shortest path from a single source to every other node in a graph with non negative edge weights. It keeps a tentative distance for each node and repeatedly settles the unsettled node whose tentative distance is smallest.
Decrease key
When the algorithm relaxes an edge and finds a shorter way to reach a neighbor, it lowers that neighbor's stored distance. With a binary heap this is a decrease key operation: locate the entry and bubble it up to its new position. Many implementations skip true decrease key and instead push a fresh entry, then ignore stale entries when they pop.
- Pop the closest unsettled node.
- Relax each outgoing edge.
- If a neighbor improves, decrease its key in the heap.
Why greedy is safe
Because weights are non negative, once a node is popped with the minimum tentative distance, no later path can do better. That node is permanently settled.
Key idea
Dijkstra greedily settles the nearest unsettled node and uses a priority queue with decrease key to track improving distances, which is correct precisely because no edge weight is negative.