{"id":"arxiv/2610.10596","url":"https://arxiv.org/abs/2610.10596","tags":["cs.DS","cs.DM","math.OC"],"score":0,"title":"Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness","domain":"cs.DS","source":"arxiv","authors":["Shengbao Wang"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}