Dijkstra's algorithm — greedy, priority queue, O((V+E) log V) — no negative edges: Worked examples

This page runs Dijkstra through every kind of graph it can meet. Before touching a single number, we lay out a scenario matrix: a grid of the different situations the algorithm must survive. Then each worked example is tagged with the exact matrix cell it covers, so by the end no scenario is left unshown.

Two words we lean on the whole way — let us pin them to pictures first.

Before any example, let us fix the priority-queue vocabulary so that "pop", "push" and "skip" mean something concrete rather than assumed knowledge.

Definition The priority queue (PQ) and its three verbs

A priority queue here is a min-heap (see Priority Queue (Binary Heap)): a box of $(k ey, v er t e x)$ pairs that always hands back the pair with the smallest key first.

push $(k, v)$ ::: drop a new pair into the box. Cost $O (lo g V)$ .
pop ::: remove and return the pair with the smallest $k ey$ . Cost $O (lo g V)$ .
skip ::: pop a pair and immediately discard it without processing (used for stale entries, defined in Ex 5).

The exact loop every example below silently runs:

dijkstra(G, s):
    dist[v] = INF for all v;   dist[s] = 0
    prev[v] = NULL for all v        # for path recovery, Ex 9
    PQ = min-heap with (0, s)
    while PQ not empty:
        (d, u) = PQ.pop()
        if d > dist[u]: continue    # <-- the stale-skip line, Ex 5
        for each edge (u, v, w):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                PQ.push((dist[v], v))
    return dist, prev

Every "Pop X", "Relax", "push" and "skip" in the examples refers to a line of this pseudocode.

The scenario matrix

#	Case class	What makes it tricky	Covered by
C1	Greedy re-relaxation	closest vertex later improves a farther one	Ex 1
C2	Tie in distances	two vertices pop with equal $d i s t$	Ex 2
C3	Unreachable vertex	no path exists → stays $\infty$	Ex 3
C4	Zero-weight edge	non-negative but weight $= 0$	Ex 4
C5	Stale heap entry	a vertex sits twice in the PQ	Ex 5
C6	Self-loop / parallel edges	degenerate edges that must not corrupt $d i s t$	Ex 6
C7	Negative edge (failure)	limiting case where Dijkstra is wrong	Ex 7
C8	Real-world word problem	translate a story into a weighted graph	Ex 8
C9	Exam twist: recover the path	not just distances, but the route itself	Ex 9
C10	Complexity / degenerate size	dense vs sparse limiting behaviour	Ex 10

Every cell C1–C10 gets its own example below.

Ex 1 — Greedy re-relaxation (cell C1)

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

Figure s01 (alt text): four nodes A, B, C, D on a blueprint grid. The amber arrow $A \to B$ is labelled $4$ ; the cyan arrows $A \to C (1)$ , $C \to B (2)$ , $C \to D (5)$ , $B \to D (1)$ form the alternative route. Walk-through: trace the two ways into $B$ — the single amber arrow (cost $4$ ) versus the two cyan arrows through $C$ (cost $1 + 2 = 3$ ). Then trace into $D$ — the winning path threads $A \to C \to B \to D$ , hopping along cyan arrows only. Keep this picture in view for every step below.

There are two ways to reach $B$ : the direct amber edge $A \to B$ costing $4$ , and the two-hop cyan path $A \to C \to B$ costing $1 + 2 = 3$ . The greedy order is what discovers the cheaper one.

Init. $d i s t [A] = 0$ , all else $\infty$ . Push $(0, A)$ . Why this step? We know we are at the source for free; everything else is unknown.
Pop A(0). Relax $A \to C$ : $0 + 1 = 1 < \infty$ → $d i s t [C] = 1$ . Relax $A \to B$ : $0 + 4 = 4 < \infty$ → $d i s t [B] = 4$ . Why this step? From a finalized vertex we push improvements to neighbours.
Pop C(1) — the heap holds $B (4), C (1)$ ; the minimum is C. Relax $C \to B$ : $1 + 2 = 3 < 4$ → $d i s t [B] = 3$ . Relax $C \to D$ : $1 + 5 = 6$ → $d i s t [D] = 6$ . Why this step? Popping the closest vertex first is the greedy rule; it lets C fix B before B is ever finalized (the red-hot moment the figure's cyan path beats the amber one).
Pop B(3). Relax $B \to D$ : $3 + 1 = 4 < 6$ → $d i s t [D] = 4$ .
Pop D(4). No outgoing edges. Done.

Answer: $d i s t = {A : 0, B : 3, C : 1, D : 4}$ .

Ex 2 — A genuine tie (cell C2)

Pop S(0). $d i s t [A] = 3$ , $d i s t [B] = 3$ . Why this step? The source is finalized first; relaxing its two edges seeds A and B with equal guesses — this is what manufactures the tie we want to study.
Pop the min of {A(3),B(3)}. Ties are broken arbitrarily (say A). Relax $A \to T$ : $3 + 2 = 5$ → $d i s t [T] = 5$ . Why this step? Correctness never depends on which equal-key vertex we pop; both give the same true distance.
Pop B(3). Relax $B \to T$ : $3 + 2 = 5$ , not $< 5$ , so no update. Why this step? The second symmetric route offers no improvement (the < guard rejects an equal value), proving the tie did not corrupt $d i s t [T]$ .
Pop T(5). Done. Why this step? T has no outgoing edges; popping it just confirms its finalized distance and drains the queue.

Answer: $d i s t [T] = 5$ , unaffected by tie order.

Ex 3 — Unreachable vertex (cell C3)

Init. $d i s t [A] = 0$ , $d i s t [B] = d i s t [C] = d i s t [Z] = \infty$ . Why this step? Everyone except the source starts "unknown" ( $\infty$ ); Z's sticky note begins exactly like every other far city — we cannot yet tell it is an island.
Pops: A→ relax B ( $2$ ); B→ relax C ( $4$ ); C→ nothing. Why this step? The core loop only ever pushes vertices we can reach; each pop finalizes a reachable city and relaxes its outgoing edges, following the chain A→B→C to its natural end.
Z is never pushed — nothing ever relaxes an edge into it. Why this step? Z has in-degree $0$ , so no relaxation ever names it; the queue empties without touching Z, leaving its $\infty$ untouched. That $\infty$ is the correct "no path" report.

Answer: $d i s t = {A : 0, B : 2, C : 4, Z : \infty}$ . The $\infty$ is the correct report: "no path exists."

Ex 4 — Zero-weight edge (cell C4)

Pop A(0). Relax $A \to B$ : $0 + 0 = 0$ → $d i s t [B] = 0$ . Relax $A \to C$ : $5$ → $d i s t [C] = 5$ . Why this step? A $0$ edge is still valid; $B$ is genuinely reachable at cost $0$ .
Pop B(0) (min of {B(0),C(5)}). Relax $B \to C$ : $0 + 1 = 1 < 5$ → $d i s t [C] = 1$ . Why this step? Non-negativity (including exactly $0$ ) keeps the greedy invariant intact — no infinite loops, since $0$ edges never reduce a finalized value.
Pop C(1). Done. Why this step? C has no outgoing edges; its pop simply finalizes the improved distance $1$ and empties the queue, confirming the free hop through B paid off.

Answer: $d i s t [C] = 1$ .

Ex 5 — Stale heap entry (cell C5)

This is the lazy heap in action (defined up top): we never decrease a key — we push a fresh better pair and let the outdated one rot in the heap. A stale entry is a pair $(d, v)$ whose $d$ is larger than the current $d i s t [v]$ because a better pair overtook it. The guard that detects staleness is exactly the pseudocode line from the top of this page:

(d, u) = PQ.pop()
if d > dist[u]: continue     # d is stale -> skip

Pop A(0). Push B with key $9$ and C with key $1$ . Heap: ${(1, C), (9, B)}$ . Why this step? Standard relaxation from the source seeds both neighbours' first guesses.
Pop C(1). Relax $C \to B$ : $1 + 1 = 2 < 9$ → $d i s t [B] = 2$ , push $(2, B)$ . Heap now: ${(2, B), (9, B)}$ — B is in twice. Why this step? C is closer than B(9), so it pops first and discovers a cheaper route into B; lazy deletion means we push $(2, B)$ rather than editing the old $(9, B)$ .
Pop $(2, B)$ . Run the guard: d > dist[B]? $2 > 2$ ? No → process B, finalize at $2$ . Why this step? This is B's first non-stale pop, so its $d i s t$ is now provably final.
Pop $(9, B)$ . Run the guard: d > dist[B]? $9 > 2$ ? Yes → continue, skip. Why this step? The $(9, B)$ entry is a fossil from step 1, superseded by $(2, B)$ . Skipping it avoids re-relaxing B's neighbours from a wrong, inflated distance.

Answer: $d i s t [B] = 2$ ; the stale $(9, B)$ pop does nothing.

Ex 6 — Self-loop and parallel edges (cell C6)

Pop A(0). Relax self-loop $A \to A$ : $0 + 3 = 3 < 0$ ? No → no update. Why this step? A self-loop with non-negative weight can never beat $d i s t [A] = 0$ ; the relaxation guard < rejects it. (A negative self-loop would loop forever — another reason we forbid negatives.)
Relax parallel edges $A \to B$ : first $0 + 5 = 5$ → $d i s t [B] = 5$ ; then $0 + 2 = 2 < 5$ → $d i s t [B] = 2$ . Why this step? Dijkstra treats parallel edges independently; the cheaper one simply wins via the same $<$ guard.
Pop B(2). Done. Why this step? B has no outgoing edges; its pop finalizes the cheaper parallel-edge value $2$ and drains the queue, confirming neither degenerate edge corrupted the result.

Answer: $d i s t = {A : 0, B : 2}$ ; degenerate edges harmless.

Ex 7 — Negative edge, the failure case (cell C7)

We want ONE clean graph that makes Dijkstra return the wrong answer, and a crisp reason. To appreciate why the counter-example must be built carefully, note two facts first:

Figure s02 (alt text): four nodes S, A, B, C on a blueprint grid. Cyan arrows $S \to A (0)$ , $A \to C (2)$ , $S \to B (3)$ ; the amber arrow $B \to A (- 5)$ is the dangerous negative edge. Walk-through: the amber arrow points back into A from B. But A sits at distance $0$ from S and gets popped almost immediately — before B (distance $3$ ) is ever processed. By the time the amber edge is relaxed, A is already stamped "done", so its improvement never propagates to C. The caption at the bottom states the wrong vs true value.

Pop S(0). Relax $S \to A$ : $0 + 0 = 0$ → $d i s t [A] = 0$ . Relax $S \to B$ : $0 + 3 = 3$ → $d i s t [B] = 3$ . Why this step? Standard seeding of the source's neighbours; nothing negative touched yet.
Pop A(0) — it is the heap minimum, so A is finalized at $0$ . Relax $A \to C$ : $0 + 2 = 2$ → $d i s t [C] = 2$ . Why this step? Greedy pops the closest vertex; A(0) beats B(3), so A is declared done now — this premature finalization is the trap.
Pop B(3). Relax $B \to A$ : $3 + (- 5) = - 2 < 0$ → this wants to set $d i s t [A] = - 2$ . But standard Dijkstra never re-opens a finalized vertex, so the improvement to A is ignored, and C is never re-relaxed. Why this step? This is the exact line where the correctness proof's " $\geq 0$ " assumption dies: a later negative edge tried to improve an already finalized vertex, and the algorithm has no mechanism to accept it.
Heap empties. Dijkstra returns $d i s t [C] = 2$ . Why this step? Termination is normal; the bug is silent — no crash, just a wrong number.

Dijkstra's output: $d i s t [C] = 2$ . True answer: $S \to B \to A \to C = 3 - 5 + 2 = 0$ .

Ex 8 — Real-world word problem (cell C8)

Translate: vertices = {Depot,P1,P2,P3}, weights = minutes (all $\geq 0$ , so Dijkstra is valid).

Pop Depot(0). $d i s t [P 1] = 6$ , $d i s t [P 2] = 2$ . Why this step? Depot is the source; relaxing its two outgoing flights seeds P1 and P2 with first guesses.
Pop P2(2). Relax P2→P1: $2 + 3 = 5 < 6$ → $d i s t [P 1] = 5$ . Relax P2→P3: $2 + 7 = 9$ → $d i s t [P 3] = 9$ . Why this step? P2 is nearest; going through it lets us reconsider P1 (5 beats the direct 6).
Pop P1(5). Relax P1→P3: $5 + 4 = 9$ , not $< 9$ → no change. Why this step? We must check whether the cheaper route into P1 opens a cheaper route onward to P3; here it ties, so the < guard rejects it.
Pop P3(9). Done. Why this step? P3 has no outgoing edges; its pop finalizes the fastest time and drains the queue.

Answer: fastest time to P3 is $9$ minutes (route Depot→P2→P3, tying Depot→P2→P1→P3 = $2 + 3 + 4 = 9$ ).

Ex 9 — Exam twist: recover the actual path (cell C9)

Add one array, initialized to a sentinel: prev[v] = NULL for every vertex (this is the prev line already in the pseudocode at the top). NULL means "no known predecessor yet", so any vertex still holding NULL at the end is either the source or unreachable.

Relax $A \to C$ → $p r e v [C] = A$ . Relax $A \to B$ → $p r e v [B] = A$ . Why this step? Each successful relaxation stamps who provided the current best route into the neighbour.
$C \to B$ improves B → overwrite $p r e v [B] = C$ . $C \to D$ → $p r e v [D] = C$ . Why this step? When a cheaper route into B is found (via C), the predecessor must be rewritten to match the new $d i s t [B]$ .
$B \to D$ improves D → overwrite $p r e v [D] = B$ . Why this step? D's best route now threads through B, so its predecessor updates in lock-step with $d i s t [D]$ .
Reconstruct by walking prev from D backwards until we hit a vertex whose prev is NULL (that is the source $A$ ): $D p r e v B p r e v C p r e v A (NULL)$ . Reverse → $A \to C \to B \to D$ . Why this step? Following predecessors reverses the discovery; stopping at NULL guarantees we halt at the source and never chase a dangling pointer.

Answer: shortest path is $A \to C \to B \to D$ , total weight $4$ .

Ex 10 — Complexity in limiting cases (cell C10)

Sparse, $E = V$ : $(V + E) lo g V = (V + V) lo g V = 2 V lo g V = O (V lo g V)$ . Why this step? With few edges the vertex term matters; heap operations scale with $V$ .
Dense, $E = V^{2}$ : $(V + V^{2}) lo g V = O (V^{2} lo g V)$ . Why this step? Edges dominate; every edge may push once, each push $O (lo g V)$ .
Degenerate limit — Fibonacci heap gives $O (E + V lo g V)$ : dense becomes $O (V^{2})$ , beating $O (V^{2} lo g V)$ by a $lo g$ factor via amortized $O (1)$ decrease-key from the Priority Queue (Binary Heap) upgrade. Why this step? In the densest limit the $lo g V$ factor is the only thing left to shave; swapping the heap removes it, which is exactly when the upgrade pays off.

Answer: (a) $O (V lo g V)$ , (b) $O (V^{2} lo g V)$ with a binary heap.

Every cell, checked

Recall Did we hit all ten cells?

C1 Ex1 (re-relax) · C2 Ex2 (tie) · C3 Ex3 (unreachable) · C4 Ex4 (zero edge) · C5 Ex5 (stale) · C6 Ex6 (self-loop) · C7 Ex7 (negative fails) · C8 Ex8 (word problem) · C9 Ex9 (path recovery) · C10 Ex10 (complexity). Plus the read-once disclaimer covering directed/undirected and overflow. No gaps.

Connections

Dijkstra (Hinglish) — the parent note
Bellman-Ford algorithm — the fix for Ex 7's negative edges
BFS — the zero/unit-weight limit of these scenarios
Priority Queue (Binary Heap) — the stale-entry mechanism of Ex 5
Greedy algorithms — why the re-relax order (Ex 1) is provably safe
A* search — add a heuristic to the same relaxation loop
Johnson's algorithm — reweight so Dijkstra survives negatives