Worked examples — Link state routing — OSPF, Dijkstra

---

The scenario matrix

Think of each row as a type of trap a question can spring. Every worked example below is tagged with the cell it covers.

#	Case class	What's tricky	Covered by
C1	Plain positive graph	baseline, one clear answer	Example 1
C2	Tie in tentative distances	two nodes share the minimum — which to pick?	Example 2
C3	Two equal-cost shortest paths (ECMP)	OSPF keeps both	Example 3
C4	Disconnected / unreachable node	some $d[v]$ stays $\infty$	Example 4
C5	Zero-cost edge (degenerate)	$w=0$, is greedy still safe?	Example 5
C6	Negative edge (Dijkstra FAILS)	greedy finalizes too early	Example 6
C7	Link failure → re-flood → recompute	the map changes, routes change	Example 7
C8	Real-world word problem	translate "delays" into a graph	Example 8
C9	Exam twist: directed graph	$A\to B\ne B\to A$	Example 9

---

Example 1 — C1: the baseline positive graph

Forecast: Guess the cheapest way from $A$ to $D$ before reading on. Is it the direct-looking $A\to B\to D$, or a sneaky detour through $C$?

1. Init. $d[A]=0$, everything else $=\infty$, finalized set $S=\varnothing$. Why this step? We must start knowing nothing except that the source is $0$ away from itself.
2. Pick $A$ (min $=0$). Relax its edges: $d[B]=4$, $d[C]=1$. Why this step? Greedy invariant: the smallest tentative distance is already final, so $A$ is safe to lock, then we update its neighbours.
3. Pick $C$ (min $=1$). Relax: $d[B]=\min (4,1+2)=3$, $d[D]=\min (\infty ,1+5)=6$. Why this step? $C$ now has the smallest tentative value. Relaxing improves $B$ from $4$ to $3$ (path $A\to C\to B$ beats direct $A\to B$).
4. Pick $B$ (min $=3$). Relax: $d[D]=\min (6,3+1)=4$. Why this step? Going $A\to C\to B\to D$ costs $4$, cheaper than $A\to C\to D=6$.
5. Pick $D$ (min $=4$). All finalized.

Verify: Enumerate the three simple paths to $D$: $A\to B\to D=5$, $A\to C\to D=6$, $A\to C\to B\to D=1+2+1=4$. Minimum is $4$. ✓ Path: $A\to C\to B\to D$.

---

Example 2 — C2: a tie for the minimum

Forecast: After finalizing $A$, both $B$ and $C$ sit at $3$. Does it matter whether we grab $B$ or $C$ first?

1. Init & pick $A$. Relax: $d[B]=3$, $d[C]=3$. A tie. Why this step? Standard init, then $A$ is the unique minimum.
2. Break the tie arbitrarily — pick $B$. Relax: $d[D]=\min (\infty ,3+2)=5$. Why this step? When two nodes share the minimum, Dijkstra's correctness does not depend on which you pick; both are already final because their tentative value is smallest.
3. Pick $C$ (still $=3$, final). Relax: $d[D]=\min (5,3+2)=5$. No change. Why this step? $C$'s distance was already finalized-worthy; relaxing just confirms $D$.
4. Pick $D$ ($=5$). Done.

Verify: Had we picked $C$ first, $d[D]$ would compute $3+2=5$ then be confirmed by $B$ — identical. Both orderings give $d[B]=d[C]=3$, $d[D]=5$. ✓ Tie-breaking never changes the distances (it may change which path is stored).

---

Example 3 — C3: two equal-cost shortest paths (OSPF's ECMP)

Forecast: One next-hop, or two?

1. List the shortest paths to $D$. $A\to B\to D=5$ and $A\to C\to D=5$. Why this step? ECMP keeps every path whose total cost equals the minimum — here both equal $5$.
2. Read off first hops. Path 1's first hop is $B$; path 2's is $C$. Why this step? The forwarding table stores destination → next-hop (from the parent note). Two equal paths ⇒ two next-hops.
3. Forwarding entry. Dest D → next-hop {B, C}, cost 5 — traffic to $D$ can be split across $B$ and $C$. Why this step? This is exactly OSPF's load-balancing feature; a distance-vector protocol without ECMP would keep only one. See OSPF Areas for how OSPF scales this.

Verify: Both paths cost $3+2=5$; there are exactly $2$ equal-cost paths, hence $2$ next-hops. ✓

---

Example 4 — C4: an unreachable node

Forecast: A number, or a symbol?

1. Init. $d[A]=0$, $d[B]=d[C]=d[E]=\infty$. Why this step? Standard start; $\infty$ means "no known path yet."
2. Pick $A$, relax: $d[B]=2$. Pick $B$, relax: $d[C]=4$. Why this step? The reachable part fills in normally.
3. Now pick the minimum unfinalized. Only $E$ remains, at $\infty$. Why this step? No edge ever relaxed $E$, so nothing lowered it.
4. Result: $d[E]=\infty$ — $E$ is unreachable; no routing-table entry is created for it. Why this step? A finite algorithm cannot invent a path that the topology graph does not contain.

Verify: No sequence of edges connects $A$ to $E$, so the true shortest distance is $\infty$, matching the algorithm. ✓

---

Example 5 — C5: a zero-cost edge (degenerate but legal)

Forecast: Does a zero-weight edge break the greedy invariant like a negative one would?

1. Init & pick $A$. Relax: $d[B]=0$, $d[C]=3$. Why this step? The edge $A\text{–}B$ has cost $0$, so $B$ is exactly as far as $A$.
2. Pick $B$ (min $=0$, tied with $A$ which is already done). Relax: $d[C]=\min (3,0+3)=3$. No change. Why this step? Greedy needs weights $\ge 0$ — and $0$ is $\ge 0$, so finalizing $B$ at $0$ is safe. A later edge can never lower an already-final distance because all remaining edges add $\ge 0$.
3. Pick $C$ ($=3$). Done.

Verify: $d[B]=0$ (a free hop), $d[C]=3$. Paths $A\to C$ and $A\to B\to C$ both cost $3$. Zero weights preserve the non-negativity precondition, so no failure. ✓

---

Example 6 — C6: a negative edge that BREAKS Dijkstra

Forecast: Dijkstra will "finalize" $B$ early. Guess whether the finalized value is the true shortest distance.

1. Init & pick $A$. Relax: $d[B]=1$, $d[C]=4$. Why this step? Standard start.
2. Pick $B$ (min $=1$) and finalize it. Why this step? Greedy assumes the smallest tentative value is final. This is the fatal assumption when a negative edge exists.
3. Pick $C$ ($=4$). Relax $C\to B$: $d[B]$ would become $4+(-3)=1$. But $B$ is already finalized, so Dijkstra never revisits it. Why this step? This is precisely where Dijkstra loses correctness — it refuses to improve a locked node.
4. Dijkstra's output: $d[B]=1$. True shortest: $A\to C\to B=4-3=1$… equal here, but consider the general danger below.

True computation (correct tool): the shortest distance to $B$ is $\min (1,4-3)=1$. In this instance both happen to be $1$, so the number matches — but the path Dijkstra records ($A\to B$) is not the only optimum, and if $A\to C$ were $3$ then $A\to C\to B=0<1$ would be missed entirely.

Verify: With $A\to C=4$: $\min (1,4-3)=1$. With a hypothetical $A\to C=3$: true $\min (1,3-3)=0$, but Dijkstra still reports $1$ — wrong. Negative weights ⇒ use Bellman–Ford Algorithm, never Dijkstra. ✓

---

Example 7 — C7: a link fails, LSPs re-flood, routes recompute

Forecast: By how much does the distance to $D$ jump when the good link dies?

1. Before failure — run Dijkstra. Pick $A$: $d[B]=1$, $d[C]=1$. Pick $B$: $d[D]=1+1=2$. $d[D]=2$ via $A\to B\to D$. Why this step? Baseline shortest path over the healthy topology.
2. Link $B\text{–}D$ fails. $B$ notices via missing HELLOs, builds a new LSP with a higher sequence number, floods it. Why this step? From the parent: the newest LSP (highest sequence) replaces the old map on every router. See Routing Table vs Forwarding Table for what gets rebuilt.
3. Every router rebuilds the graph — edge $B\text{–}D$ is gone — and reruns Dijkstra. Pick $A$: $d[B]=1$, $d[C]=1$. Pick $C$: $d[D]=1+4=5$. Now $d[D]=5$ via $A\to C\to D$. Why this step? With the fast link removed, the only route to $D$ is the expensive $C$ side.
4. Result: $d[D]$ jumps from $2$ to $5$; next-hop for $D$ changes from $B$ to $C$.

Verify: Before: $\min (A\text{-}B\text{-}D=2,A\text{-}C\text{-}D=5)=2$. After removing $B\text{–}D$: only $A\text{-}C\text{-}D=5$ remains. ✓

---

Example 8 — C8: a real-world word problem

Forecast: Straight down $A\to B\to D$, or the two-short-hops route through $C$?

1. Translate to a graph. Latencies are edge weights (all positive ⇒ Dijkstra is valid). Directed because a one-way latency need not equal the reverse. Why this step? "Minimise total delay" = "shortest path with weights = delays." This is the standard OSPF trick: cost = a link metric.
2. Run Dijkstra from $A$. Pick $A$: $d[B]=10$, $d[C]=20$. Why this step? Finalize the source, relax its out-edges.
3. Pick $B$ (min $=10$). Relax: $d[C]=\min (20,10+5)=15$; $d[D]=\min (\infty ,10+15)=25$. Why this step? $A\to B\to C$ (=$15$) beats the direct $A\to C$ (=$20$).
4. Pick $C$ (min $=15$). Relax: $d[D]=\min (25,15+5)=20$. Why this step? $A\to B\to C\to D=20$ beats $A\to B\to D=25$.
5. Pick $D$ ($=20$). Done.

Verify: Candidate routes: $A\to B\to D=25$; $A\to C\to D=25$; $A\to B\to C\to D=10+5+5=20$. Minimum $=20$ ms via $A\to B\to C\to D$. ✓ (Units: all terms are ms, summed ⇒ answer in ms.)

---

Example 9 — C9: exam twist — directed asymmetric graph

Forecast: Will the cheap $C\to B=1$ edge help lower $d[B]$?

1. Init & pick $A$. Relax out-edges of $A$ only: $d[B]=2$, $d[C]=7$. Why this step? In a directed graph you relax only edges pointing away from the current node. The $B\to A=9$ edge is irrelevant to reaching $B$ or $C$ from $A$.
2. Pick $B$ (min $=2$). Relax $B$'s out-edges: $B\to A$ (ignore, $A$ done), $B\to C=\min (7,2+2)=4$. Why this step? $A\to B\to C=4$ beats direct $A\to C=7$.
3. Pick $C$ (min $=4$). Relax $C\to B$: $d[B]=\min (2,4+1)=2$. No change. Why this step? The cheap $C\to B=1$ edge cannot help — reaching $C$ already cost $4$, so $4+1=5>2$.
4. Result: $d[B]=2$, $d[C]=4$.

Verify: Shortest to $B$: direct $A\to B=2$ (the reverse edge and the $C\to B$ detour are both longer). Shortest to $C$: $A\to B\to C=4<A\to C=7$. ✓ Direction matters: $B\to A=9$ never enters the computation.

---

Active recall

Recall Which scenarios break Dijkstra, and what replaces it?

• Negative edge weights ::: Dijkstra may finalize a node too early and miss a cheaper later path ⇒ use Bellman–Ford Algorithm.
• Zero-weight edge ::: Fine — $0\ge 0$ keeps the greedy invariant valid.
• Tie in tentative distances ::: Pick either; final distances are identical (path stored may differ).
• Unreachable node ::: Its $d$ stays $\infty$; no forwarding entry.
• Two equal-cost shortest paths ::: OSPF keeps both (ECMP), two next-hops.

---

Connections

• Link state routing — OSPF, Dijkstra — the topic this deep-dives
• Dijkstra's Algorithm — the core algorithm exercised here
• Bellman–Ford Algorithm — the fix for Example 6's negative edge
• Distance Vector Routing — the alternative family
• Flooding — how the failed-link LSP in Example 7 propagates
• OSPF Areas — how ECMP (Example 3) scales in real OSPF
• Routing Table vs Forwarding Table — what recomputation rebuilds