Computer Network & Network Security System — Network Layer, NEC licence examination syllabus (Nepal Engineering Council).
Routing Algorithms: the actual maths behind "shortest path"
The most numerical-heavy topic in networking — and the one where marks are won by tracing a table cleanly rather than by knowing the definition.
Dijkstra's Algorithm — the link-state approach
Dijkstra finds the shortest path from ONE source to every other node, always settling the closest unvisited node next. It needs the whole topology in advance, which is why it belongs to link-state routing where every router is given a full map.
Dijkstra's algorithm:
1. distance to source = 0, all others = infinity
2. pick the unvisited node with the smallest known distance
3. relax its neighbours: if going through this node is shorter,
update that neighbour's distance
4. mark this node visited — its distance is now FINAL
5. repeat until every node is visited
Step 4 is the part that makes it work, and the part worth being able to justify: once a node is settled, its distance never changes again. That holds only because every edge weight is non-negative — you can never reach a settled node more cheaply by a longer detour. This is exactly the assumption Bellman-Ford drops.
Worked example — trace it as a table
Graph (undirected weights):
A --4-- B
| / |
2 1 5
| / |
C --8-- D --2-- E
| |
+-------10------+
Start at A. Track [settled | tentative distances].
Step Settle A B C D E
────────────────────────────────────────
init — 0 ∞ ∞ ∞ ∞
1 A 0 4 2 ∞ ∞ relax B(4), C(2)
2 C 0 4 2 10 12 via C: D=2+8, E=2+10
3 B 0 4 2 9 12 via B: D=4+5=9 beats 10
4 D 0 4 2 9 11 via D: E=9+2=11 beats 12
5 E 0 4 2 9 11 nothing left to improve
Final shortest distances from A:
B = 4 C = 2 D = 9 E = 11
💡 Two marks are commonly lost here. First, settle nodes in order of smallest tentative distance, not alphabetically — the order above is A, C, B, D, E, and writing A, B, C, D, E gives the wrong intermediate table even when the final answer survives. Second, show the table after every step; a correct final answer with no working usually scores less than a traced table with one arithmetic slip.
Bellman-Ford — the distance-vector approach
Bellman-Ford needs no map. Each router knows only its direct neighbours and what those neighbours claim their distances are, and the correct answer emerges from repeating that exchange. That is what makes it usable in a real network where no router is told the whole topology.
Relaxation, applied to every edge:
distance[v] = min( distance[v], distance[u] + weight(u,v) )
Repeat over ALL edges, (number of nodes − 1) times.
Why n−1 passes: a shortest path can contain at most n−1
edges, and each pass extends every path by at least one
edge — so n−1 passes is enough to find any of them.
It also tolerates negative edge weights and can detect a negative cycle, which Dijkstra cannot. Real networks have no negative link costs, so this matters for the algorithm's theory rather than for routing practice.
Count-to-infinity: the failure mode that shaped RIP
Distance vector's weakness follows directly from routers believing their neighbours without knowing why a neighbour believes what it does.
A ── B ── C all links cost 1
A knows: C is 2 hops away, via B
B knows: C is 1 hop away, directly
The B–C link fails.
B looks for another route to C.
A is advertising "I can reach C, cost 2".
B believes it: "then I can reach C, cost 3 — via A"
A sees B's new cost and updates: "C costs 4, via B"
B updates again: 5. A: 6. B: 7 …
Neither knows that A's original route went THROUGH B.
The cost climbs one step at a time towards infinity.
🔧 This is why RIP defines a maximum hop count and treats anything beyond it as unreachable — the limit exists to make the count terminate, not because networks that size are impossible. Split horizon, which forbids advertising a route back to the neighbour you learned it from, prevents the simplest two-node version of this loop.
Flooding
The simplest approach and the most wasteful: every router forwards every incoming packet on every link except the one it arrived on. It needs no routing table at all and guarantees delivery if any path exists, which is why it is used for the initial distribution of link-state information — a router that does not yet have a map cannot route by one.
Left unchecked it never terminates, so packets carry a hop limit and routers discard duplicates they have already seen.
Commonly confused
Dijkstra and Bellman-Ford. Not just two ways to the same answer. Dijkstra needs the full topology and non-negative weights; Bellman-Ford needs neither, and pays for it in convergence speed.
Link state and distance vector. The algorithm follows from the information available: full map allows Dijkstra, neighbour gossip forces Bellman-Ford.
Hop count and cost. RIP counts hops, so a four-hop fibre path looks worse than a two-hop slow link. OSPF uses a cost derived from bandwidth, which is one of the reasons it replaced RIP.
Rapid revision
Dijkstra: settle the smallest tentative distance, relax its neighbours, repeat. Settled distances are final because weights are non-negative.
Trace the table at every step — that is the graded artefact.
Bellman-Ford: relax every edge, n−1 times. Works from neighbours alone, tolerates negative weights.
Count-to-infinity comes from believing a neighbour's cost without knowing its route. Hop limits and split horizon contain it.
Flooding needs no table, which is why link-state maps are distributed that way.
Syllabus points
Shortest path — Dijkstra (numerical)
Flooding
Distance vector — Bellman-Ford (numerical)
Link state routing
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.