Exercise 3: Why cache and database End Up Numerically Correct Anyway — Possible Solution ==================================================================== GIVEN ------------------------------ Step 5's Dijkstra run: cache=13, database=-2 (after correction), response=14 (WRONG - true value is 2). WHAT HAPPENED, STEP BY STEP ------------------------------ 1. cache is popped and finalized at distance 13. At this exact moment, cache's own value (13) is never revised again by anything later - nothing in the rest of the graph points INTO cache, so no future relaxation could ever change it. cache=13 is correct simply because nothing ever challenges it again. 2. database is popped and finalized EARLIER, at distance 10 (via api). Because api->database(2) is processed before cache is even reached, database gets provisionally finalized at 10. 3. Only after that does cache get popped (13) and relax cache->database: 13+(-15)=-2, which IS less than database's current value of 10 - so database's dist[] table ENTRY gets overwritten to -2, even though database was already marked visited. WHY database'S TABLE VALUE (-2) IS CORRECT DESPITE BEING "TOO LATE" ------------------------------ This is exactly the same situation as this chapter's own Step 5 finding and Chapter 6's original B/D counterexample: the dist[] table is just a plain lookup table with no concept of "already finalized." The relaxation step happily overwrites database's entry to -2 regardless of the visited flag. Since nothing else in the graph could offer database yet another correction after this one, -2 happens to be the true correct shortest distance to database - the overwrite, though never "acted on" by the algorithm's own traversal, still lands on the right number. WHY response IS WRONG DESPITE database'S NUMBER BEING RIGHT ------------------------------ response was already relaxed via database's STALE value of 10 back in the step where database was first finalized (10+4=14). Because database was already marked visited by the time its own -2 correction arrived, database's outgoing edge to response was never relaxed again using the corrected value - the algorithm only ever relaxes a vertex's neighbors at the exact moment that vertex is popped and finalized, and database was popped and finalized before its true value was known. RESULT ------------------------------ cache is correct because nothing ever needed to correct it. database is correct by coincidence - its table entry got overwritten by a relaxation that was never actually used to propagate anything further. response is wrong because it was the one vertex that actually depended on database's value at the specific moment database was used to relax outward - and that moment happened before the correct value existed. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation distinguishes three genuinely different reasons a vertex's dist[] entry can be correct or wrong - never needing correction at all, receiving a correction that's simply never propagated further, and depending on a value before it was corrected - rather than treating "some numbers are right and some are wrong" as an unexplained inconsistency, reusing this chapter's own step-by-step reasoning pattern rather than just re-stating Chapter 6's original conclusion.