Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.10596
curl -X POST /api/v1/records/arxiv/2610.10596/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.10596/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'