Visual walkthrough — Dijkstra's algorithm — greedy, priority queue, O((V+E) log V) — no negative edges

We use the parent's tiny graph the whole way through so nothing sneaks up on you:

A→B(4), A→C(1), C→B(2), C→D(5), B→D(1), source A.

---

Step 1 — What is a graph, really?

WHAT. A graph is just dots (we call them vertices or nodes — think "cities") joined by arrows (we call them edges — think "one-way roads"). Each arrow carries a number, its weight, meaning "how many minutes this road costs to walk."

WHY. Before we talk about "shortest," we must agree on what a "path" and its "length" even are. A path from A to D is any sequence of arrows you can follow, front-to-back, from A to D. Its length is the sum of the weights of the arrows you used — not the number of arrows, the sum of their minute-costs.

PICTURE. Look at the board. Four cities A B C D. The arrow A→C is labelled $1$, so walking directly from A to C costs $1$ minute. The arrow A→B costs $4$. There are two ways to reach B from A: the direct road A→B (cost $4$), or the detour A→C→B (cost $1+2=3$). The detour is cheaper even though it uses more roads — hold onto that, it's the whole game.

---

Step 2 — The sticky-note array, and $\infty$ as "no idea yet"

WHAT. We keep one number per city, written $dist[v]$ — the best time we currently believe. At the start we know nothing, so every city gets $dist=\infty$ ("infinity" = "unreachable as far as I know"), except the source: $dist[A]=0$, because standing at home costs zero minutes.

WHY $\infty$ and not, say, $999$? Because $\infty$ is a value that any real path beats. The first time we find any route to a city, its finite cost is automatically smaller than $\infty$, so the sticky note updates. Using a big-but-finite number risks a real path being larger than it and getting rejected.

PICTURE. Four sticky notes on the board: A = 0 (chalk-yellow, we're sure), B = ∞, C = ∞, D = ∞ (all pale, "unknown"). Nothing is finalized yet — a note can still shrink.

---

Step 3 — Relaxation: the one move we ever make

WHAT. The only action Dijkstra performs is relaxing an edge $u\to v$:

WHY "relax"? The word comes from a tight rubber band: the distance estimate for $v$ is stretched too high, and passing through $u$ lets it relax down to a truer, smaller value. It can only ever go down, never up.

PICTURE. We stand at $A$ (with $dist[A]=0$) and relax its two out-roads. Road A→C(1): $0+1=1<\infty$, so $C$'s note drops to $1$. Road A→B(4): $0+4=4<\infty$, so $B$'s note drops to $4$. The blue arrows show the estimate falling from $\infty$ onto a real number.

---

Step 4 — The priority queue: always grab the nearest unfinished city

WHAT. After Step 3 two cities have finite guesses: C = 1 and B = 4. Which do we trust and "finalize" first? We use a priority queue (a min-heap): a gadget that always hands back the smallest stored (distance, city) pair fast. We pop the minimum: C(1).

WHY the smallest? This is the heart of the whole method. Claim: the city with the smallest current estimate can never be improved later, so it is safe to declare done. Steps 5–6 prove exactly this. For now, feel it: C = 1 is the closest thing to home; no other route can sneak in under $1$ because every road costs $\ge 0$, so any other first step already costs at least as much.

PICTURE. The heap drawn as a little sorted rack: C(1) at the front (chalk-pink highlight = "about to pop"), B(4) behind it. The arrow pulls C out and stamps it FINAL.

---

Step 5 — Why the popped city is truly done (the proof, drawn)

WHAT. We prove the invariant: the moment we pop the min-distance city $u$, its note $dist[u]$ already equals the true shortest distance $\delta (u)$.

WHY (by contradiction — drawn on the board). Suppose not: some secret cheaper path to $u$ exists with true cost $\delta (u)<dist[u]$. That secret path starts inside the finalized region (it starts at $A$, which is done) and must eventually step out of it. Let $y$ be the first not-yet-finalized city on that secret path, entered from a finalized city $x$ via the road $x\to y$.

PICTURE. The board is split: a shaded "DONE" blob (finalized cities) and the outside. The secret pink path crosses the border exactly at the road $x\to y$.

Now chase the inequalities, each pinned to the picture:

$dist[y]\underset{\text{we already relaxed }x\to y}{\underbrace{\le \delta (x)+w(x,y)}}=\underset{y\text{’s true dist along this path}}{\underbrace{\delta (y)}}\underset{\text{rest of path costs }\ge 0}{\underbrace{\le \delta (u)}}<\underset{\text{our assumption}}{\underbrace{dist[u]}}$

• First $\le$ ::: since $x$ is finalized, we already relaxed $x\to y$, so $y$'s note is at most that sum.
• The $=$ ::: on the shortest path, $\delta (y)$ is precisely $\delta (x)$ plus the one road to $y$.
• Second $\le$ ::: the only place non-negativity is used — the remaining road-costs from $y$ to $u$ are all $\ge 0$, so getting further can't get cheaper.
• Final $<$ ::: our false assumption.

So $dist[y]<dist[u]$. But we popped $u$ because it was the minimum, meaning $dist[u]\le dist[y]$. Contradiction. Therefore no secret cheaper path exists — $u$ is genuinely done. ∎

---

Step 6 — Finalizing C fixes B (greed paying off)

WHAT. C is done at $1$. We relax C's out-roads. C→B(2): $1+2=3<4$, so B's note drops from 4 to 3 — the detour beats the direct road, exactly as we teased in Step 1. C→D(5): $1+5=6<\infty$, so D = 6.

WHY this is the payoff. Had we finalized B at $4$ first (its old estimate), we'd have locked in a wrong answer. Popping the closest city first — C before B — is what let C's cheaper route reach B before B was frozen. Greed and correctness are the same act here.

PICTURE. C (now FINAL) fires two blue relaxation arrows: one crosses out B's 4 and writes 3; one turns D's ∞ into 6.

---

Step 7 — Finish the flood, and the stale-entry twist

WHAT. The heap now holds B(3), B(4) (a leftover!), D(6). Pop the min B(3), finalize it, relax B→D(1): $3+1=4<6$, so D = 4. Next pop is the stale B(4): but B is already done and $4>dist[B]=3$, so the guard if d > dist[u]: continue skips it. Finally pop D(4), no out-roads, done.

WHY the stale skip exists. We used a lazy heap: rather than editing B's old entry when it improved, we just pushed a fresh B(3) and left the old B(4) behind. So a city can appear more than once. The first pop carries its true value; any later pop carries an outdated, larger d — we recognize and discard it.

PICTURE. The heap rack shows B(3) popped (final), then B(4) popped but stamped STALE / SKIP in pink because $4>3$, then D(4) popped final.

Final answer, matching the parent's table exactly: $dist[A]=0,dist[B]=3,dist[C]=1,dist[D]=4$

---

Step 8 — Degenerate cases you must never be surprised by

WHAT / WHY / PICTURE, three corner scenarios on one board:

1. Unreachable city. If no path exists to some city, its note stays $\infty$ forever — the flood never arrives. (That's correct output, not a bug.)
2. Zero-weight edge $w=0$. The relaxation and proof still hold: "$\ge 0$" includes $0$. Two cities can share the same distance; the heap just pops them in some tie-order.
3. Self-loop or already-shorter route. Relaxing u→v when $dist[u]+w\ge dist[v]$ changes nothing — the < test simply fails, note untouched.

Recall Why we never revisit a finalized city

Because Step 5 proved the popped city is truly optimal. Once optimal, no future relaxation can lower it (all roads $\ge 0$), so re-examining it is wasted work. Contrast: with even one negative edge that guarantee vanishes — see Bellman-Ford algorithm.

---

The one-picture summary

Everything above, compressed: cities flood outward from A in the order water reaches them — A(0) → C(1) → B(3) → D(4) — each finalized only when popped as the current minimum, each relaxing its out-roads to shrink neighbors' sticky notes, with the "$\ge 0$" road-costs guaranteeing no finalized note ever moves again.

Recall Feynman: the whole walkthrough in plain words

Home is A. Every house has a sticky note saying "fastest time I know," starting at 0 for home and "unknown (∞)" for everyone else. I repeat one move: look at all houses I haven't finalized, walk to the nearest one, stamp it done — because roads only ever cost time (never give it back), nothing can later beat that nearest house's time. Then from that just-finalized house I check each outgoing road: if going through here is faster than a neighbor's current note, I lower the neighbor's note. A min-heap is just a fast way to always grab the nearest un-done house. Sometimes a house's note improves before I visit it, so it might sit in the heap twice; when I pop an old, too-big copy I recognize it's stale and toss it. When the heap empties, every sticky note holds the true shortest time. For our graph the water reaches A→C→B→D at times 0, 1, 3, 4.

---

Connections

• Yeh visual walkthrough Hinglish mein
• Priority Queue (Binary Heap) — the min-heap doing the "nearest first" pops
• Greedy algorithms — Step 5 is the exchange/invariant argument
• BFS — Step 4's ordering becomes a plain queue when all weights are $1$
• Bellman-Ford algorithm — what to reach for when the "$\ge 0$" step dies
• A* search — Dijkstra with a heuristic nudging the flood toward the goal
• Prim's algorithm — same pop-min-relax skeleton, different relaxation
• Johnson's algorithm — reweight to non-negative, then run this walkthrough