Intuition The one core ideaLink state routing means every router builds the same complete map of the network, then privately computes the shortest path to everywhere . To understand it you need just three picture-ideas: a graph (dots joined by weighted lines), a shortest path (the cheapest walk along those lines), and the greedy rule that grows finalized distances outward from a source.
Before you can read the parent note, you must be able to see every symbol it throws at you. This page builds each one from nothing — plain words first, then a picture, then why the topic needs it. Read top to bottom; each block leans on the one above.
The parent note says routers, cities, postcards. Underneath all of that is one clean mathematical object: a graph .
Definition Graph — nodes and edgesA graph is a set of nodes (dots) connected by edges (lines). Here:
a node = a router (or city). We give each one a name letter: A , B , C , …
an edge = a physical link between two routers.
That's it. A graph is "dots and the lines between them."
Intuition Why the topic needs thisA router doesn't care what a cable is made of. It only cares "who am I connected to, and how expensive is that hop?" A graph throws away everything irrelevant and keeps exactly that. Every LSP the parent describes is really one node announcing its own edges .
Two flavours matter:
Undirected edge : the line works both ways (A–B is the same as B–A). Worked Example 1 in the parent uses undirected links.Directed edge : a one-way arrow u → v last hop into v u
w ( u , v ) w ( u , v ) cost (a number) of using the edge from node u v u v
In OSPF this number is a link cost (roughly, "how slow / expensive is this link").
It is always a positive number in OSPF — remember this, it decides everything later.
Intuition Why a number and not just "connected/not"?If every edge cost the same, "shortest path" would just mean "fewest hops." Real networks have fast and slow links, so we attach a number to each edge. The whole point of Dijkstra is to add these numbers up and find the smallest total.
w ( u , v ) Why it feels right: we call it a "cost" or "length." Why it's wrong: it's an abstract number — could be based on bandwidth, delay, or an admin's choice. Fix: treat w
Definition Path and path lengthA path from s v A → B → C → D length of a path = the sum of the weights of every edge on it.
Worked example Reading a path lengthIn the parent's graph, the path A → B → C w ( A , B ) + w ( B , C ) = 2 + 1 = 3 A → C w ( A , C ) = 5 A → B → C 3 cheaper than going direct (cost 5 d [ C ] 5 3
To travel a whole route you pay for every edge you use, one after another. Adding them is just "total the bill." The shortest path is the route with the smallest total bill.
This is the single most important notation in the parent note. It looks scary; it is not.
d [ v ] v d [ v ] v the length of the cheapest path we have found so far from the source s v
"Tentative" means "our current best guess — it may still shrink."
The square brackets [ v ] v
Intuition Why keep a "best so far" box?We discover better routes as we explore. Instead of recomputing everything, each node keeps its current best number and lowers it whenever we find something cheaper. When we're done exploring, that box holds the true shortest distance.
d [ s ] = 0 d [ others ] = ∞
d [ s ] = 0 itself costs nothing — you're already there.d [ v ] = ∞ ∞ any route to v any real path we discover will be smaller and will replace it.
Intuition Why not just leave it blank?Using ∞ ∞ everything is smaller than infinity .
min ( a , b ) min ( a , b ) a b min ( 3 , 5 ) = 3
Now the parent's central formula. Let's earn every piece:
d [ v ] ← min ( d [ v ] , d [ u ] + w ( u , v ) )
Read it piece by piece:
d [ u ] + w ( u , v ) u plus one more hop from u v one specific route to v u → v d [ v ] min v not use that last hop.min ( … ) The arrow ← store this new value into d [ v ]
← = Why it feels right: both use an equals-looking sign. Fix: ← updates a box (do this, then move on); = asserts two things are equal forever. Relaxation is an update.
S ∅ S set of finalized nodes — nodes whose d [ ⋅ ] locked , guaranteed correct, never to change.
==∅ empty set : a set containing nothing. We start with S = ∅ nobody is finalized.
u ∈ / S u not in the finalized set" (still tentative).
Intuition Why a "locked" set?Dijkstra grows a frontier of certainty outward from the source. Once a node is locked, we never re-examine it — that's what makes the algorithm efficient. The figure shows S
Intuition The claim, stated with our symbolsAmong all nodes not in S u d [ u ] Claim: that d [ u ] final shortest distance — lock it.
Why? Any other route to u S w ≥ 0 add cost, so it can't beat the value we already have. This is the exact reason the parent stresses non-negative weights : a negative edge could secretly shrink a "finalized" number, and the lock would be a lie.
Recall Where does the parent use each symbol?
w ( A , B ) = 2 d [ C ] 5 → 3 B S = { A } { A , B } ∞
O ( ⋅ ) V E log
==V E
log V logarithm of V V log V ==O ( … ) no faster than this, ignoring constant factors." It answers "how does the running time scale as the network gets huge?"
Intuition Why we care about scaling, not exact timeA backbone can have thousands of routers. We don't need the exact microseconds; we need "does it stay fast as V O (( V + E ) log V )
d of v: best distance so far
Link State Routing and OSPF
Each foundation on the left must be solid before the arrow it feeds. If any box is fuzzy, the parent note will feel like magic — go back and re-read that block.
Test yourself — you should be able to answer each before reading the parent:
What is a graph, in one sentence? A set of nodes (dots) joined by edges (lines); here nodes are routers and edges are links.
What does w ( u , v ) The cost/weight of the edge from u v
What is the length of a path? The sum of the weights of all edges on that path.
What does the box d [ v ] The length of the cheapest path found so far from the source to v
Why do we initialise d [ s ] = 0 d [ others ] = ∞ The source reaches itself for free; unknown nodes start "infinitely far" so any real route replaces it.
What does min ( a , b ) Returns the smaller of the two numbers.
Explain the relaxation rule in words. d [ v ] d [ u ] + w ( u , v ) u u → v
What is the set S ∅ S ∅ S
Why must edge weights be non-negative for the greedy pick to be valid? A detour out of S
What does O (( V + E ) log V ) How the running time scales with V E
