Dijkstra's algorithm

The shortest-path method link-state routers run: the closest tentative node's distance is final, so it is fixed next.

Edsger Dijkstra designed it in 1956 to demonstrate the ARMAC computer and published it in 1959. OSPF and IS-IS name it as the basis of their route calculation, which is why routers call it SPF, shortest path first.

The 1959 note in Numerische Mathematik is three pages long and solves two problems, the minimum spanning tree first and the shortest path second. It builds the shortest paths from the starting node in order of increasing length, so each node's distance is settled before any longer one. In 1993 Dijkstra wrote that he designed it without pencil and paper, over coffee on a café terrace in Amsterdam, only for a demonstration.

RFC 2328 states the router's version: at each iteration the candidate closest to the root is guaranteed to be shortest, joins the tree, and its neighbours are examined. When two paths tie, both next hops are kept, so strictly the result is not a tree. The specification does not require this exact method, only that any other algorithm produce an identical tree.

The guarantee needs non-negative costs, and OSPF goes further: every interface cost must be greater than zero. RFC 1195 gives the cost of the computation as the square of the number of nodes, lower on sparse networks, and FRRouting's documentation calls it mostly negligible on modern CPUs. What routers do limit is how often it runs: RFC 8405 standardises a back-off that delays SPF when events arrive close together.

Also known as: shortest path first, spf algorithm, dijkstra, spf calculation, shortest-path tree

Sources

← All glossary entries