Why One Cheap Shortcut Backwards Breaks the Whole Map
Subtitle: Smallest-first is a proof, not a habit.
- Section 1 - What gets settled:
- dist[source] = 0; all others = infinity
- Pull the smallest unsettled distance
- Relax every edge leaving that vertex
- Mark the pulled vertex final
- Section 2 - Why smallest-first works:
- Other unsettled nodes cost at least as much
- Non-negative next edges cannot get cheaper
- The heap asks: who is provably done?
- Runtime: O(E log V)
- Section 3 - Where a negative edge breaks proof:
- S to A = 1; S to B = 1; B to A = -1
- A to C = 1; true A = 0 and C = 1
- Settling A early reports A = 1 and C = 2
- The downstream error spreads silently
- Section 4 - Test and choose honestly:
- Put an edge after the damaged vertex
- Re-pushing can hide a weak counterexample
- Negative weights: use Bellman-Ford
- Equal weights: breadth-first search