Exercise 2: Why Dijkstra Never Needs to Reconsider a Finalized Vertex — Possible Solution ==================================================================== THIS CHAPTER'S OWN GREEDY ASSUMPTION ------------------------------ Dijkstra always finalizes whichever not-yet-finalized vertex currently has the smallest known distance in the priority queue. The whole algorithm depends on one guarantee holding every single time this happens: that smallest current distance is already the TRUE shortest distance to that vertex, and nothing discovered later can ever beat it. WHY THAT GUARANTEE HOLDS WHEN EVERY WEIGHT IS NON-NEGATIVE ------------------------------ Suppose vertex X is about to be popped with the smallest distance currently in the queue. Any other possible path to X not yet accounted for would have to pass through some other vertex Y that is still in the queue (or not yet reached at all). Because every edge weight is non-negative, the length of a path through Y can only be Y's own distance PLUS however much more is added by the remaining edges to X - it can never be LESS than Y's own distance. But Y's own distance is, by definition of the priority queue, already greater than or equal to X's distance (that's exactly why X was popped first, not Y). So any path routed through Y is already guaranteed to be at least as long as X's current distance - it cannot possibly beat it. There is no way left for a shorter route to X to still be hiding in the unexplored part of the graph. WHY THIS BREAKS WITHOUT THE NON-NEGATIVE ASSUMPTION ------------------------------ A negative edge weight destroys exactly this guarantee: a path through Y CAN end up shorter than Y's own distance once a large negative edge is added on top of it, even though Y's distance was larger than X's at the moment X was finalized. This is exactly this chapter's own counterexample - C's distance (4) was larger than B's first-found distance (1) at the moment B was finalized, but the edge C->B(-10) made the true route through C shorter than B's already-finalized value once it was actually explored. RESULT ------------------------------ With non-negative weights, "smallest distance currently in the queue" and "true shortest distance" are guaranteed to coincide at the moment of finalization, so revisiting a finalized vertex would be redundant work - it can never actually improve. Negative weights break that coincidence, which is exactly why Dijkstra requires non-negative weights to be correct. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation grounds the "no need to reconsider" behavior in the specific mathematical guarantee non-negative weights provide - that any competing path can only be equal to or longer than a finalized vertex's own distance - rather than simply restating that Dijkstra "just doesn't revisit vertices" as an unexplained rule.