A packet crossing the internet is steered by routing algorithms that every router runs to decide where to send it next. Two families dominate the syllabus: distance vector and link state. Aspirants lose marks by blurring the two and by never hand-running Dijkstra. Let us separate them cleanly and build a shortest-path tree step by step.
Routing versus forwarding
These two words are not synonyms, and examiners test the difference. Routing is the network-wide process of computing good paths and filling each router's routing table; it is relatively slow and runs in the background. Forwarding is the local, per-packet action of moving a packet from an input port to the correct output port using the table that routing already built; it happens in nanoseconds. Routing builds the map, forwarding follows it.
Distance vector routing
In distance vector routing, each router knows only its directly connected neighbours and the cost to reach them. It maintains a vector of estimated distances to every destination and periodically shares that whole vector with its neighbours. Each router then updates its own estimates from what neighbours report.
The Bellman-Ford update
The core rule is the Bellman-Ford equation. For a router x reaching destination y, the estimated cost is the minimum over each neighbour v of (cost from x to v) plus (v's advertised cost to y):
Dx(y) = min over v of ( c(x, v) + Dv(y) )
Each router recomputes this whenever a neighbour's vector changes, and readvertises if its own estimate changed. The estimates converge to true shortest paths, but only gradually, because news spreads one hop per exchange.
Count-to-infinity
Distance vector's weakness is the count-to-infinity problem. When a link fails, the bad news travels slowly, and two routers can keep incrementing their estimates of a now-unreachable destination, each believing the other still has a path. The count climbs step by step toward infinity before convergence. Partial fixes include split horizon (do not advertise a route back to the neighbour you learned it from) and poison reverse. This slow, loop-prone convergence is the standard exam critique of distance vector.
Link state routing
Link state routing takes the opposite approach. Each router discovers the cost to its own neighbours, then floods that information (a link-state packet) to every router in the network. After flooding, every router holds an identical, complete map of the topology and independently computes shortest paths using Dijkstra's algorithm.
Flooding means each router forwards a received link-state packet on all links except the one it arrived on, so the map propagates network-wide quickly. Because every router has the full topology, link state converges faster and avoids count-to-infinity, at the cost of more memory and flooding overhead.
A worked Dijkstra shortest-path tree
Take five routers, A through E, with these link costs:
A-B: 2, A-C: 5
B-C: 1, B-D: 2
C-E: 3, D-E: 1
Run Dijkstra from source A. Start with distance to A as 0 and every other node as infinity, then repeatedly finalise the nearest unfinalised node and relax its neighbours.
Finalise A at 0. Relax neighbours: B becomes 2, C becomes 5.
The nearest unfinalised is B at 2. Relax from B: C via B is 2 + 1 = 3, which beats 5, so C becomes 3; D via B is 2 + 2 = 4.
Next nearest is C at 3. Relax from C: E via C is 3 + 3 = 6, so E becomes 6.
Next is D at 4. Relax from D: E via D is 4 + 1 = 5, which beats 6, so E becomes 5.
Finalise E at 5. All nodes done.
The final shortest distances from A are: B = 2, C = 3, D = 4, E = 5. The shortest-path tree uses the edges that gave each final value: A-B, B-C, B-D, and D-E. Note E is reached through D, not directly through C, because A-B-D-E costs 5 while A-B-C-E costs 6.
[DIAGRAM: The five-node graph with all edge weights, and the shortest-path tree from A highlighted in bold: edges A-B, B-C, B-D, and D-E, with each node labelled by its final distance 0, 2, 3, 4, 5.]
Draw this once and confirm every relaxation by hand. Exams give you exactly such a weighted graph and ask for the shortest-path tree or the distance to one node.
Where RIP and OSPF fit
The two families map onto two real protocols you should name. RIP (Routing Information Protocol) is a distance vector protocol using hop count as its metric, simple but limited and slow to converge. OSPF (Open Shortest Path First) is a link state protocol that floods link states and runs Dijkstra, scaling to large networks with faster convergence. RIP is the textbook distance vector example; OSPF is the textbook link state example.
How routing algorithms are tested in GATE, NET, and placements
GATE CS sets Dijkstra numericals (compute the shortest-path tree or a specific distance on a given graph), distance-vector table-update problems (apply Bellman-Ford for a round or two), and count-to-infinity tracing. Distinguishing routing from forwarding is a recurring conceptual item.
UGC NET Computer Science favours the comparisons: distance vector versus link state, which protocol is which, and what flooding and split horizon mean. Definitions and protocol mapping score here.
Placement and company tests ask which algorithm the internet's interior routing uses and why link state converges faster, expecting the full-topology-versus-neighbour-only contrast.
The short version
Routing computes paths, forwarding moves packets. Distance vector shares distance vectors with neighbours via Bellman-Ford and suffers count-to-infinity; link state floods the full topology and runs Dijkstra, converging faster. Map them to RIP and OSPF, then hand-run Dijkstra until the tree is automatic. Routing sits directly on the addressing you meet in IP Addressing and Subnetting Explained and feeds the services in Application Layer Protocols: DNS, HTTP, and email, so study the stack together. The full Computer Networks learn module and GATE Guidance by Sanchit Sir sequence routing with the rest of the network layer. Learn the Dijkstra trace cold, and routing questions become dependable marks.
