Dijkstra's algorithm

Picture spilling water at one spot on a map of roads, where water flows along roads at speeds set by each road's cost. The water reaches the nearest town first, then the next-nearest, spreading outward and always settling the closest unfinished town next. Dijkstra's algorithm computes least-cost paths in exactly this 'closest first' spirit, and it is the engine inside every link-state routing protocol.

It runs from one source node and grows a set of 'finished' nodes whose true least cost from the source is known. Each node has a tentative distance, starting at 0 for the source and infinity for everyone else. Repeatedly: pick the unfinished node with the smallest tentative distance, mark it finished (its distance is now final), and for each of its neighbors check whether going through this newly finished node gives a cheaper route — if so, lower that neighbor's tentative distance (this step is called relaxation). When all nodes are finished, you have the least-cost path to every destination, plus the first hop along each, which is what goes in the forwarding table.

Why it works: because the algorithm always finalizes the globally closest remaining node, and costs are non-negative, no later discovery can ever beat a path you have already finalized. That guarantee is why link-state routers, each holding the same complete map, can independently run Dijkstra and arrive at consistent, loop-free routes. OSPF literally calls its computation SPF (shortest-path-first), which is Dijkstra.

An honest caveat: Dijkstra requires non-negative link costs — negative costs break the 'closest first' guarantee (that is Bellman-Ford's territory). It also needs the full graph, so it only suits link-state routing, not distance-vector. With a good priority queue it runs efficiently, but a router still recomputes when the topology changes, which is why frequent flapping is expensive.