Exercise 3: Why B Came Out Correct But D Came Out Wrong — Possible Solution
====================================================================

GIVEN
------------------------------
Graph: A->B(1), A->C(4), C->B(-10), B->D(100)
Dijkstra's run: B ends up at -6 (correct) but D ends up at 101
(incorrect - the true value is 94).

WHAT ACTUALLY HAPPENED, STEP BY STEP
------------------------------
1. B is popped and finalized FIRST, at distance 1 (the direct edge
   A->B, smaller than C's 4). At this moment, D is immediately
   relaxed using B's distance: 1+100=101. D is now sitting in the
   queue at 101.

2. C is popped and finalized next, at distance 4. Relaxing C->B
   finds 4+(-10)=-6, which IS less than B's current recorded
   value of 1 - so the dist[] table entry for B gets overwritten
   to -6.

3. But B was already marked visited/finalized back in step 1. The
   corrected (-6, B) queue entry that gets pushed is later popped
   and immediately discarded, because the "already visited" check
   skips it. B is never re-finalized, and - critically - B's
   OUTGOING edges are never relaxed again using the corrected -6
   value.

WHY B'S NUMBER LOOKS CORRECT ANYWAY
------------------------------
The dist[] dictionary itself has no concept of "finalized" - it is
just a plain lookup table, and step 2's relaxation happily
overwrites dist['B'] to -6 even though the vertex itself is
already marked visited. So the FINAL PRINTED TABLE shows B=-6,
which happens to be numerically correct - but this correctness is
essentially accidental: it's a side effect of a relaxation that
was never actually "acted on" by the algorithm's own traversal
logic.

WHY D'S NUMBER IS WRONG
------------------------------
D was only ever relaxed once, back in step 1, using B's ORIGINAL
(uncorrected) distance of 1 - because that was the only moment B
was actually popped as the current vertex and used to relax its
neighbors. Once B was finalized, it was never popped and used to
relax neighbors again, so D never received the benefit of B's
later correction to -6. D is stuck with the stale value 1+100=101,
instead of the true -6+100=94.

RESULT
------------------------------
B's dist[] entry got quietly corrected as a side effect of
relaxation math, but that correction was never propagated forward
because Dijkstra only relaxes a vertex's neighbors AT THE MOMENT
that vertex is popped and finalized - and B was popped and
finalized before the correct value was ever known.

WHY THIS WORKS AS AN ANSWER
------------------------------
The explanation traces exactly which step updates which value and
why, distinguishing "the dist[] table entry changed" (which
happened for B, coincidentally producing the right number) from
"the algorithm actually used that value to relax B's neighbors"
(which never happened, since B was already finalized) - showing
precisely why one number self-corrected while the other stayed
wrong, rather than treating both as equally broken or equally
fine.