Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness

Abstract

Dijkstra's algorithm is traditionally classified as a greedy algorithm. We argue that this classification misrepresents the mechanism by which the algorithm determines shortest paths. We present a direct global-to-local proof of correctness. At each iteration, the algorithm identifies a shortest path over the entire set of paths whose endpoints remain unsolved. This global minimum is necessarily a shortest path to its own endpoint. More fundamentally, the algorithm uses already determined shortest paths to establish one additional shortest path at each iteration. We identify this progression as dynamic programming. A three-step exclusion proof shows how the full path space is reduced to frontier candidates, how relaxation removes inferior alternatives, and why minimum extraction yields the global minimum. The choice is thus determined by a global comparison, not by an optimistic local greedy choice. We conclude that the algorithm is more accurately characterized by dynamic programming and deterministic path exclusion than by the traditional greedy classification.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.