Metraipolis › archive › dc_cc867bf7e121
Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness — arXiv:2610.10596
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.10596
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:28:09.851Z
- SHA-256 of the archived text
5c07810dd1705c37abb7670f58d1b6191086c4e87bd40858e8b3bd59539112dc- Stable URL of this page
https://metraipolis.com/documento/dc_cc867bf7e121
How to cite
Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness — arXiv:2610.10596 — arXiv (en), https://arxiv.org/abs/2610.10596 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cc867bf7e121 (Metraipolis archive dc_cc867bf7e121, sha256 5c07810dd1705c37abb7670f58d1b6191086c4e87bd40858e8b3bd59539112dc)
BibTeX
@misc{dccc867bf7e121,
title = {Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness — arXiv:2610.10596},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.10596},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cc867bf7e121; sha256 5c07810dd1705c37abb7670f58d1b6191086c4e87bd40858e8b3bd59539112dc},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10596. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2610.10596 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T05:52:31.689Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).