Dijkstra's Algorithm

Dijkstra's algorithm is the standard greedy approach to shortest-path problems, but the reason it works — and the exact condition under which it stops working — comes down to one operation: relaxation. This paper walks through that core idea, the six-step algorithm built on top of it, and a clean Python implementation using a min-heap.

• Defines relaxation as the update rule dist[v] = dist[u] + w(u, v) whenever that path beats the current known distance to v.
• Explains why the algorithm's greedy 'once visited, never revisited' guarantee only holds when every edge weight is non-negative.
• Breaks the algorithm into six steps: initialization, selection, exploration, relaxation, finalization, and termination.
• Implements the algorithm in Python with heapq as a priority queue, giving O((E + V) log V) performance versus O(V²) for a brute-force unordered list.
• Notes that Bellman-Ford is the correct fallback the moment negative edge weights enter the graph.