Link state routing — OSPF, Dijkstra: Visual walkthrough

We will use the same tiny map the parent used, so you can check every number yourself:

A–B = 2, A–C = 5, B–C = 1, B–D = 7, C–D = 3. Source = A.

Step 1 — What is a "map" to a computer?

WHAT. A router's map is just dots joined by lines, and every line has a number written on it. A dot is a router (we call it a node). A line is a direct link between two routers (we call it an edge). The number on a line is its cost — think "how many minutes to drive that road."

WHY. Before we can talk about the shortest route we must agree what a "route" and its "length" even are. A route is a chain of edges from start to finish; its length is the sum of the numbers on those edges. Nothing more mysterious than adding up road times.

PICTURE. Look at the five circles and the labelled lines. The number beside each line is what we add up.

Figure — Link state routing — OSPF, Dijkstra

Step 2 — The one quantity we track: $d [v]$

WHAT. For every node $v$ we keep a single number, written $d [v]$ , meaning "the shortest distance we have found so far from the source to $v$ ." Read $d [v]$ as "d of v" — a labelled box hanging under each dot.

$d [v] = smallest sum of edge-costs best total cost from the source to node v known right now$

WHY. We can't compute all routes at once — there are too many. Instead we keep one running best guess per node and improve it as we learn more. Everything Dijkstra does is: lower these guesses until they can't drop any further.

WHY these starting values. We set $d [A] = 0$ because the distance from A to itself is zero — you're already there. Every other node starts at $\infty$ (infinity), meaning "no route found yet." Infinity is just a placeholder for "unreachable so far"; any real number beats it, so the first real path we find will always replace it.

$d [A] = 0, d [B] = d [C] = d [D] = \infty$

PICTURE. Each dot now wears its box. A's box says $0$ ; the rest say $\infty$ .

Step 3 — The one move: relaxing an edge

WHAT. Suppose $u$ already has a good distance $d [u]$ , and there is an edge $u \to v$ costing $w (u, v)$ . "Relaxing" that edge asks a single question: is going to $v$ through $u$ cheaper than the best I knew for $v$ ? If yes, update $d [v]$ .

$d [v] \leftarrow min (old best to v d [v], cost to reach u d [u] + one more hop u \to v w (u, v))$

Read the pieces where they sit: $d [u] + w (u, v)$ is "cost to get to $u$ , then step across the last road to $v$ ." The $min$ keeps whichever is smaller — the old route, or this new "via- $u$ " route.

WHY. Think about the very last road on the true shortest path to $v$ . Either that last road is $u \to v$ (then the cost is $d [u] + w$ ), or it isn't (then the old $d [v]$ still stands). These two cases cover every possibility, so taking the smaller of the two can never miss the real answer — it can only get better or stay the same. This is why relaxation is the only update rule we ever need.

PICTURE. The arrow shows the "via $u$ " route being compared with the direct box on $v$ ; the smaller number wins and gets written in.

Step 4 — The greedy pick, and why it is safe

WHAT. We grow a set $S$ of finalized nodes — nodes whose $d$ is now permanently correct. At each round we look at all nodes not yet in $S$ and pick the one with the smallest $d$ . We declare that node finalized and add it to $S$ .

WHY (the whole engine of the proof). Take the not-yet-finalized node $u$ with the smallest tentative $d [u]$ . Could a sneakier, cheaper path to $u$ exist? Any such path starts inside $S$ and must leave $S$ at some first node $x \in / S$ . But $d [x] \geq d [u]$ (we picked $u$ as the smallest!), and every remaining edge on that path adds cost $\geq 0$ . So that sneaky path costs at least $d [u]$ — it can't be shorter.

Notice the load-bearing phrase: edges add cost $\geq 0$ . That is the only reason greedy works. Kill that assumption and the proof dies (Step 6).

PICTURE. The shaded blob is $S$ . Any escaping path (dashed) must cross the boundary at some $x$ whose box is already $\geq d [u]$ , then only pile on more.

Step 5 — Run it: pick A, relax A's roads

WHAT. A has the smallest $d$ (it's $0$ ), so finalize A: $S = {A}$ . Now relax A's two edges:

Edge $A \to B$ , cost $2$ : $d [B] = min (\infty, 0 + 2) = 2$ .
Edge $A \to C$ , cost $5$ : $d [C] = min (\infty, 0 + 5) = 5$ .

WHY. These are the first real routes we discover, so both $\infty$ flags fall away. Nothing points to D from A directly, so $d [D]$ stays $\infty$ .

PICTURE. A is now solid (finalized). Its boxes for B and C light up with their new values.

Finalized	d[A]	d[B]	d[C]	d[D]
{A}	0	2	5	∞

Step 6 — Pick B, and watch C improve (the key moment)

WHAT. Smallest unfinalized box is $d [B] = 2$ → finalize B: $S = {A, B}$ . Relax B's edges:

Edge $B \to C$ , cost $1$ : $d [C] = min (5, 2 + 1) = 3$ . (improved!)
Edge $B \to D$ , cost $7$ : $d [D] = min (\infty, 2 + 7) = 9$ .

WHY C drops $5 \to 3$ . The path $A \to B \to C$ costs $2 + 1 = 3$ , beating the direct $A \to C = 5$ . Relaxation caught it: $min (5, 3) = 3$ . This is the moment that shows why we don't trust a first guess — a detour can be shorter.

PICTURE. The green route A→B→C is highlighted; C's box is crossed out from 5 and rewritten to 3.

Finalized	d[A]	d[B]	d[C]	d[D]
{A,B}	0	2	3 (via B)	9 (via B)

Step 7 — Pick C, finish D, and stop

WHAT. Smallest unfinalized is $d [C] = 3$ → finalize C: $S = {A, B, C}$ . Relax C's edge:

Edge $C \to D$ , cost $3$ : $d [D] = min (9, 3 + 3) = 6$ . (improved!)

Now the only node left is D with $d [D] = 6$ ; finalize it. $S$ = all nodes → stop.

WHY D becomes 6 not 9. Route $A \to B \to C \to D$ costs $2 + 1 + 3 = 6$ , cheaper than $A \to B \to D = 9$ . Again $min (9, 6) = 6$ picks the detour.

PICTURE. The full shortest-path tree from A lights up: A→B (2), B→C (1), C→D (3).

Finalized	d[A]	d[B]	d[C]	d[D]
all	0	2	3	6

Final distances from A: B = 2, C = 3, D = 6. These match the parent note exactly.

Step 8 — The degenerate case: a negative road breaks everything

WHAT. Suppose we secretly change one edge to a negative cost. Say $A \to C$ costs $5$ but there is a magic road $C \to B$ costing $- 4$ . Dijkstra would finalize B at $d [B] = 2$ in Step 6... but the route $A \to C \to B$ costs $5 + (- 4) = 1$ , which is cheaper — yet B was already locked!

WHY it breaks. In Step 4 the safety proof used "every remaining edge adds cost $\geq 0$ ." A negative edge violates that: an escaping path can lose cost later, so the "nearest" node is no longer guaranteed final. Greedy finalization becomes a lie.

THE FIX. For maps with negative costs you must use Bellman–Ford Algorithm, which re-relaxes every edge many times and never "locks" a node early. Real OSPF link costs are always positive (they come from bandwidth), so Dijkstra is perfectly valid there — see Distance Vector Routing for where Bellman–Ford lives instead.

PICTURE. B is shown wrongly finalized at 2 while the red negative-edge path sneaks in at 1 — the contradiction.

The one-picture summary

Everything above, on one canvas: the frozen set $S$ growing, boxes dropping via relaxation, the greedy pick always grabbing the smallest box, and the final shortest-path tree from A.

Recall Feynman: tell it back in plain words

Every dot gets a little box that starts at "0" for home and "unknown" for everyone else. I keep a shrinking pile of unfinished dots. Each round I grab the unfinished dot with the smallest box — because to reach anywhere further you can only add road-time, so the nearest one's number can't get any smaller, it's final. Then I look at that dot's roads and, for each neighbor, I check: "is coming through me cheaper than what you had?" If yes, I lower their box. Repeat until every dot is finished. The one rule that makes the whole thing honest is roads never cost negative time — the moment a road could give back time, "nearest is final" stops being true and I'd need Bellman–Ford instead.

Connections

Parent: Link state routing — where this algorithm is used
Dijkstra's Algorithm — the algorithm derived here
Bellman–Ford Algorithm — the fix for negative costs (Step 8)
Distance Vector Routing — the alternative approach
Routing Table vs Forwarding Table — what the finished distances feed into