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.
Related
- Bourgain's Lambda(p) selection theorem: a greedy proof with polynomial failure bounds
- A proof of GW/DT4 conjecture on local projective plane
- A LOCAL PROOF OF LANGLANDS'S SECOND MAIN LEMMA FOR LOCAL EPSILON FACTORS OVER NONARCHIMEDEAN LOCAL FIELDS
- A LOCAL PROOF OF LANGLANDS'S FIRST MAIN LEMMA FOR LOCAL EPSILON FACTORS OVER NONARCHIMEDEAN LOCAL FIELDS
- A Local Fourier-Transform Proof of Offen's Spherical Transfer Theorem
BibTeX
@misc{wang2026dijkstra,
title = {{Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness}},
author = {Shengbao Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10596},
eprint = {2610.10596},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10596},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness
AU - Shengbao Wang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.10596
UR - https://arxiv.org/abs/2610.10596
AB - 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.
ER -