arXiv preprint ·
Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Dijkstra's algorithm is almost universally classified as a canonical greedy algorithm. This paper challenges that conventional interpretation and presents a simple, direct proof of correctness from a different viewpoint. Contrary to the widespread intuition that the algorithm repeatedly makes a local choice and thereby reaches a global optimum, we show that the logical direction can be read in exactly the opposite way: at each iteration, the algorithm identifies a globally shortest path among all paths whose destinations remain unsolved, and the endpoint of that globally shortest path is therefore solved as a ``local'' shortest-path problem. In other words, the local shortest path is obtained as an immediate consequence of a global minimum. Based on this observation, we formulate a Three-Step Exclusion Method that interprets Dijkstra's iteration as deterministic contraction of the global path space. The resulting proof highlights optimal substructure, boundary-state reduction, and dynamic-programming structure, and offers a conceptually simple alternative to the usual greedy explanation.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
On the complexity of the single-move labeled token routing problem
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
The Multiple Unicast Conjecture is False
Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation
Fast Almost-Uniform Sampling of Random $k$-SAT Solutions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.