Dijkstra: the twenty-minute algorithm your routers run every day

In 1956 Edsger W. Dijkstra designed a shortest-path algorithm on a café terrace in Amsterdam, without pencil and paper, to demonstrate a new computer; every router running Open Shortest Path First (OSPF) or Intermediate System to Intermediate System (IS-IS) computes the tree that algorithm produces. After reading, you can tell the story from his own words, run the algorithm by hand on six routers, explain why link costs must be positive and why equal costs give several next hops, and find the result and the SPF throttle on a router.

View as Markdown

Every router running Open Shortest Path First () or Intermediate System to Intermediate System () holds the same map of its area and computes from it a tree of shortest paths with itself as root (Request for Comments (RFC) 2328, section 1.1). The computation is called shortest path first (), and the standards name its author: Edsger W. Dijkstra, who designed it in 1956 and published it in 1959. After reading, you can tell where it came from in his own words, trace it by hand, explain why costs must be positive and why equal costs give several next hops, and find its result on a router.

A demonstration for the ARMAC

Dijkstra joined the Mathematical Centre in Amsterdam in March 1952 as the first Dutchman paid as a programmer, and moved there full time after his physics degree at Leiden in the spring of 1956 (EWD1166). The algorithm had a public purpose: "The algorithm for The Shortest Path was designed for the purpose of demonstrating the power of the ARMAC at its official inauguration in 1956" (EWD1166).

He gave the details in August 2001, at his home in Austin, to the researcher Philip L. Frana; the Association for Computing Machinery (ACM) published the interview, condensed, in Communications of the ACM in 2010 (Frana and Misa). The demonstration program used a map "on which I had selected 64 cities (so that in the coding six bits would suffice to identify a city)": six bits give 2 to the power 6, or 64, values.

"One morning I was shopping in Amsterdam with my young fiancée", he said; when "we sat down on the café terrace to drink a cup of coffee" he worked it out, "which I designed in about 20 minutes". He also gave a reason for its elegance: "One of the reasons that it is so nice was that I designed it without pencil and paper".

He had written down in 1993: "it is a strange thought that it was designed without pencil and paper, while I had a cup of coffee with my wife on a sunny cafe terrace in Amsterdam, only designed for a demo" (EWD1166). "Wife" is the word of 1993: he married Maria (Ria) C. Debets in 1957 (Memorial Resolution, section 0), so in 1956 she was his fiancée.

Three pages in Numerische Mathematik

A Note on Two Problems in Connexion with Graphs was received by Numerische Mathematik on 11 June 1959 and printed in volume 1, pages 269 to 271 (Dijkstra 1959, Centrum Wiskunde & Informatica (CWI) scan; Springer). It considers nodes joined by branches of given length. "Problem 1. Construct the tree of minimum total length between the n nodes" is the minimum spanning tree, designed to save copper in the backpanel wiring of the X1 computer (EWD1166). "Problem 2. Find the path of minimum total length between two given nodes P and Q" is the shortest path (Dijkstra 1959, page 270).

Why three years? In his words, "at that time, discrete algorithms had not yet acquired mathematical respectability, and there were no suitable journals", so he offered both to the new journal to help it establish itself (EWD1166).

Fame came slowly: in 1962 Ford and Fulkerson still cited inferior algorithms for the problem (Memorial Resolution, section 1). Then "I found it in the early 1960s in a German book on management science", he recalled, and "Suddenly, there was a method named after me" (Frana and Misa).

The algorithm, in 1959 and in RFC 2328

The paper's idea is one sentence: "In the solution presented, the minimal paths from P to the other nodes are constructed in order of increasing length until Q is reached" (Dijkstra 1959, page 270). Set A holds the nodes whose shortest path from P is known; set B, the nodes connected to A but not in it; set C, the rest. Each round checks whether the newest node in A offers a shorter path to a node in B, then moves the node of B nearest to P into A.

2328 says it in a router's words: "the paths to the candidate vertex that is closest to the root are guaranteed to be shortest; this vertex is added to the shortest-path tree, removed from the candidate list, and its adjacent vertices are examined"; it stops when the list is empty (RFC 2328, section 16.1). The cost D to a neighbour W is the cost already found to V plus the advertised cost of the link from V to W. When D equals the cost already listed for W, the new next hops are added to the old, and on a tie "network vertices must be chosen before router vertices in order to necessarily find all equal-cost paths" (section 16.1). Hence footnote 22: "Strictly speaking, because of equal-cost multipath, the algorithm does not create a tree".

IS-IS keeps two lists, PATHS (final) and TENT (tentative), and explains the guarantee: "paths through systems in TENT still have to be greater than x because x is minimal in TENT" (RFC 1195, Annex C.1.3).

Six routers, by hand

Six routers, R1 to R6, with router IDs 192.0.2.1 to 192.0.2.6, joined by eight point-to-point links numbered from 198.51.100.0/24, with the same cost in both directions:

Link	Cost	Link	Cost
R1 to R2	8	R3 to R5	9
R1 to R3	5	R4 to R5	4
R3 to R2	3	R4 to R6	6
R2 to R4	1	R5 to R6	2

The trace of the worked example from R1, computed on 2026-10-19 with CPython 3.13.16; lines for links back to routers already on the tree, and the candidate-list lines, are left out:

step 1: examine links of R1
  link R1-R2 cost 8: D = 0 + 8 = 8 (new candidate); first hop R2
  link R1-R3 cost 5: D = 0 + 5 = 5 (new candidate); first hop R3
  closest candidate R3 at 5 is added to the tree (its distance is now final)
step 2: examine links of R3
  link R3-R2 cost 3: D = 5 + 3 = 8 (equal to 8, add first hop; now R2/R3)
  link R3-R5 cost 9: D = 5 + 9 = 14 (new candidate); first hop R3
  closest candidate R2 at 8 is added to the tree (its distance is now final)
step 3: examine links of R2
  link R2-R4 cost 1: D = 8 + 1 = 9 (new candidate); first hop R2/R3
  closest candidate R4 at 9 is added to the tree (its distance is now final)
step 4: examine links of R4
  link R4-R5 cost 4: D = 9 + 4 = 13 (better than 14, replace); first hop R2/R3
  link R4-R6 cost 6: D = 9 + 6 = 15 (new candidate); first hop R2/R3
  closest candidate R5 at 13 is added to the tree (its distance is now final)
step 5: examine links of R5
  link R5-R6 cost 2: D = 13 + 2 = 15 (equal to 15, add first hop; now R2/R3)
  closest candidate R6 at 15 is added to the tree (its distance is now final)

In step 2, R2 costs 8 directly and 8 through R3, so both first hops are kept and everything behind R2 inherits the pair. In step 4, R5 falls from 14 to 13: a candidate's cost can still drop, a chosen router's cannot. Forwarding keeps only the first hop: "only the next hop to the destination is used in the forwarding process" (RFC 2328, section 2.2); how that entry competes in the table is in routing tables and the default gateway.

The same computation in standard-library Python, which runs unchanged in the Python playground:

import heapq

links = {("R1", "R2"): 8, ("R1", "R3"): 5, ("R3", "R2"): 3, ("R2", "R4"): 1,
         ("R3", "R5"): 9, ("R4", "R5"): 4, ("R4", "R6"): 6, ("R5", "R6"): 2}

def spf(links, root):
    nbrs = {}
    for (a, b), cost in links.items():
        nbrs.setdefault(a, []).append((b, cost))
        nbrs.setdefault(b, []).append((a, cost))
    dist, hops, done = {root: 0}, {root: set()}, []
    heap = [(0, root)]
    while heap:
        d, v = heapq.heappop(heap)
        if v in done or d > dist[v]:
            continue
        done.append(v)                      # closest candidate: its cost is final
        for w, cost in nbrs[v]:
            if w in done:
                continue
            nd = d + cost
            first = hops[v] if v != root else {w}
            if w not in dist or nd < dist[w]:
                dist[w], hops[w] = nd, set(first)
                heapq.heappush(heap, (nd, w))
            elif nd == dist[w]:
                hops[w] |= first            # equal cost: keep both first hops
    return dist, hops, done

dist, hops, order = spf(links, "R1")
for v in order[1:]:
    print(f"{v}  cost {dist[v]:2}  first hop(s) {'/'.join(sorted(hops[v]))}")
print("order added:", " ".join(order))

R3  cost  5  first hop(s) R3
R2  cost  8  first hop(s) R2/R3
R4  cost  9  first hop(s) R2/R3
R5  cost 13  first hop(s) R2/R3
R6  cost 15  first hop(s) R2/R3
order added: R1 R3 R2 R4 R5 R6

Raise the cost of R2 to R4 from 1 to 20 and run it again:

R3  cost  5  first hop(s) R3
R2  cost  8  first hop(s) R2/R3
R5  cost 14  first hop(s) R3
R6  cost 16  first hop(s) R3
R4  cost 18  first hop(s) R3
order added: R1 R3 R2 R5 R6 R4

One edit moved R4, R5 and R6 off the R2 first hop and ended their equal-cost split, and every router in the area recomputes from the same changed map.

Why costs must be positive

The rule that the closest candidate is final holds only if no link can shorten a path. The Memorial Resolution states the problem with "non-negative length" (section 1). The protocols forbid zero too: "The cost of an interface must be greater than zero" (RFC 2328, section 9), and the 1990 draft of the IS-IS standard says "The path computation algorithm utilised in this International Standard requires that all circuits be assigned a positive value for a metric" (RFC 1142, section 7.2.2).

The worked example's third run shows why. With directed links S to A cost 2, S to B cost 5 and B to A cost minus 4, Dijkstra fixes A at 2 in the first round; exhaustive relaxation finds S to B to A at 1. A node was declared final before a negative link could undercut it.

The cost travels in the router link-state advertisement (). FRRouting (FRR) sets it with ip ospf cost (1-65535), which writes the router-LSA metric used by SPF (FRRouting, OSPFv2). Derived from bandwidth, FRR's default reference of 100 Mbit/s gives every link that fast or faster a cost of 1; the OSPF primer covers the consequences.

What the standards require, and what they leave open

OSPF works in two stages: "Using the Dijkstra algorithm, a tree is formed from this subset of the link state database", the links between routers and transit networks, and stub networks are added afterwards as leaves (RFC 2328, section 16.1). The method is not mandatory: "if another algorithm is used, an identical tree must be produced", and the RFC points to an incremental SPF from a 1978 report by McQuillan, Richer and Rosen (section 16.1). OSPF for IPv6 runs the calculation on the same graph for IPv4 and IPv6 (RFC 5340, section 4.8.1).

IS-IS for IP is "a dynamic routing protocol, based on the SPF (Dijkstra) routing algorithm" (RFC 1195, section 1.1), and its annex gives the cost in words: "It has a computational complexity of the square of the number of nodes, which can be decreased to the number of links in the domain times the log of the number of nodes for sparse networks" (Annex C.1). The Memorial Resolution measures the 1959 gain the same way: earlier algorithms ran in time cubic in the size of the network, Dijkstra's in its square (section 1). RFC 1142 is quoted here only as that draft, which RFC 7142 calls of historic interest only (RFC 7142, section 1). How link state differs from the other families is in dynamic routing compared.

When the map is wrong or keeps changing

Consistent routes need identical databases on every router (RFC 1142, section 7.2.6), and OSPF requires any algorithm to yield the identical tree (RFC 2328, section 16.1). Stale or one-sided entries are filtered out: "If the LSA does not exist, or its LS age is equal to MaxAge, or it does not have a link back to vertex V, examine the next link in V's LSA" (section 16.1). A forged LSA attacks the map, not the algorithm; authentication is in the OSPF primer. Equal-cost paths are not promised in full either: "There is no requirement that a router running OSPF keep track of all possible equal-cost routes to a destination" (section 16.8).

A flapping network is the operational hazard. During multiple failures, operators want fewer SPF runs, yet "it's not possible to ensure that all routers trigger their SPF computation after the same delay", and unequal delays make micro-loops likelier and longer (RFC 8405, section 1). The standard back-off moves through three states, QUIET, SHORT_WAIT and LONG_WAIT (section 5.2), with suggested defaults of 50 ms initial delay, 200 ms short delay, 5000 ms long delay, 500 ms time to learn and 10000 ms hold-down (section 6).

FRR's OSPF has its own adaptive hold time, and its pages do not say it implements RFC 8405. timers throttle spf 200 400 10000 sets a 200 ms delay, a 400 ms initial hold time and a 10 s maximum, and each event inside the current hold time raises it by the initial hold time, up to the maximum (FRRouting, OSPFv2). FRR's IS-IS sets a minimum interval in seconds with spf-interval [level-1 | level-2] (1-120) (FRRouting, IS-IS). FRR calls the computation itself mostly negligible on modern embedded processors, even with thousands of nodes (OSPFv2). Fast failure detection, which triggers these runs, is the subject of Bidirectional Forwarding Detection (BFD).

How to see it

In FRR, with the syntax its documentation gives:

show ip ospf route [detail] [json]
show ipv6 ospf6 [vrf <NAME|all>] spf tree [json]
show isis [vrf <NAME|all>] route [level-1|level-2] [prefix-sid] [backup] [algorithm [(128-255)]]
show ip ospf

The first shows the OSPF routing table from the latest SPF run (FRRouting, OSPFv2); the second prints "the spf tree from the recent spf calculation with the calling router as the root" (FRRouting, OSPFv3); the third is the IS-IS table from its latest run (FRRouting, IS-IS); the last shows the current hold time as a multiple of the initial one (OSPFv2). In a lab, compare their costs and first hops with the script's output for the same topology.

The other Dijkstra

"When I came back from Munich, it was September, and I was Professor of Mathematics at the Eindhoven University of Technology", in 1962; he became a Burroughs Research Fellow on 1 August 1973 and moved to Austin, Texas, in the summer of 1984 (EWD1166). The same note recalls that he "thought about synchronizing primitives and designed 'semaphores' for that purpose", and that "for therapeutic reasons I wrote 'Notes on Structured Programming'". He retired from teaching in November 1999 (Memorial Resolution, section 4) and died at home in Nuenen on 6 August 2002 (Computer Sciences obituary).

His 1972 Turing Award was "For fundamental contributions to programming as a high, intellectual challenge" and for "eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness" (ACM). His line on testing dates from 1970: "Program testing can be used to show the presence of bugs, but never to show their absence" (EWD249, page EWD249-7); there is no perfect code carries it into security. His numbered notes, the EWDs, had reached number 1318 when he died (Memorial Resolution, section 6).

What to remember

Dijkstra designed the algorithm in 1956 to demonstrate the ARMAC, on a café terrace in Amsterdam, in about twenty minutes and without pencil and paper.
The 1959 paper is three pages of Numerische Mathematik and solves two problems: the minimum spanning tree, then the shortest path.
Everything rests on one guarantee: the candidate closest to the root has a final cost.
RFC 2328 names but requires only an identical tree; incremental SPF is allowed.
The guarantee needs non-negative costs, and OSPF and IS-IS require costs greater than zero.
Equal costs keep several first hops, and one metric change can move many destinations at once.
Routers delay SPF on purpose in unstable networks: RFC 8405 standardises a back-off, and FRR's OSPF uses its own adaptive hold time.