Todo roteador que roda Open Shortest Path First () ou Intermediate System to Intermediate System () guarda o mesmo mapa da sua área e calcula, a partir dele, uma árvore de caminhos mais curtos com ele mesmo na raiz (Request for Comments (RFC) 2328, seção 1.1). Esse cálculo se chama shortest path first (), e as normas dão nome ao autor: Edsger W. Dijkstra, que o criou em 1956 e o publicou em 1959. Depois da leitura, você consegue contar a origem dele nas palavras de Dijkstra, segui-lo à mão, explicar por que os custos precisam ser positivos e por que custos iguais dão vários next hops, e achar o resultado num roteador.

Uma demonstração para o ARMAC

Dijkstra entrou no Mathematisch Centrum de Amsterdã em março de 1952 como o primeiro holandês contratado como programador, e foi para lá em tempo integral ao se formar em física em Leiden, na primavera de 1956 (EWD1166). O algoritmo tinha um propósito público: "The algorithm for The Shortest Path was designed for the purpose of demonstrating the power of the ARMAC at its official inauguration in 1956", feito para a inauguração oficial do ARMAC (EWD1166).

Ele contou os detalhes em agosto de 2001, em casa, em Austin, ao pesquisador Philip L. Frana; a Association for Computing Machinery (ACM) publicou a entrevista, condensada, na Communications of the ACM em 2010 (Frana e Misa). O programa da demonstração usava um mapa "on which I had selected 64 cities (so that in the coding six bits would suffice to identify a city)", 64 cidades para que seis bits bastassem: 2 elevado a 6 dá 64.

Ele contou: "One morning I was shopping in Amsterdam with my young fiancée", às compras com a noiva; quando "we sat down on the café terrace to drink a cup of coffee", no terraço de um café, ele chegou ao algoritmo, "which I designed in about 20 minutes", em uns vinte minutos. E explicou a elegância: "One of the reasons that it is so nice was that I designed it without pencil and paper", feito sem lápis e sem papel.

Ele já tinha registrado a cena em 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", sem lápis e sem papel, num café, só para uma demo (EWD1166). Wife (esposa) é a palavra de 1993: ele se casou com Maria (Ria) C. Debets em 1957 (Memorial Resolution, seção 0), então em 1956 ela ainda era a noiva.

Três páginas na Numerische Mathematik

A Note on Two Problems in Connexion with Graphs chegou à Numerische Mathematik em 11 de junho de 1959 e saiu no volume 1, páginas 269 a 271 (Dijkstra 1959, digitalização do Centrum Wiskunde & Informatica (CWI); Springer). Trata de nós ligados por ramos de comprimento conhecido. "Problem 1. Construct the tree of minimum total length between the n nodes", a árvore geradora mínima, nasceu para economizar cobre na fiação do backplane do X1 (EWD1166). "Problem 2. Find the path of minimum total length between two given nodes P and Q", o caminho mínimo entre dois nós (Dijkstra 1959, página 270).

Por que três anos? Nas palavras dele, "at that time, discrete algorithms had not yet acquired mathematical respectability, and there were no suitable journals", faltavam prestígio matemático e revistas adequadas; ofereceu os dois à revista nova, para ajudá-la a se firmar (EWD1166).

A fama demorou: em 1962, Ford e Fulkerson ainda citavam algoritmos piores para o mesmo problema (Memorial Resolution, seção 1). Depois, "I found it in the early 1960s in a German book on management science", num livro alemão de administração, e "Suddenly, there was a method named after me", havia um método com o nome dele (Frana e Misa).

O algoritmo, em 1959 e na RFC 2328

A ideia cabe numa frase: "In the solution presented, the minimal paths from P to the other nodes are constructed in order of increasing length until Q is reached", caminhos mínimos em ordem crescente de comprimento (Dijkstra 1959, página 270). O conjunto A guarda os nós cujo caminho mais curto desde P já se conhece; B, os nós ligados a A fora dele; C, o resto. A cada rodada, verifica se o último nó de A encurta o caminho até algum nó de B e passa para A o nó de B mais próximo de P.

A 2328 diz o mesmo em linguagem de roteador: "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", o candidato mais próximo da raiz está garantido e entra na árvore; o cálculo para quando a lista esvazia (RFC 2328, seção 16.1). O custo D até um vizinho W é o custo até V mais o custo anunciado do link de V para W. Se D empata com o custo de W na lista, os next hops novos se somam aos antigos, e no empate "network vertices must be chosen before router vertices in order to necessarily find all equal-cost paths", redes antes de roteadores, para achar todos os caminhos de custo igual (seção 16.1). Daí a nota 22: "Strictly speaking, because of equal-cost multipath, the algorithm does not create a tree", a rigor, não sai uma árvore.

O IS-IS usa duas listas, PATHS (definitiva) e TENT (provisória): "paths through systems in TENT still have to be greater than x because x is minimal in TENT", nada que passe pela TENT custa menos que x (RFC 1195, anexo C.1.3).

Seis roteadores, à mão

Seis roteadores, de R1 a R6, com router IDs de 192.0.2.1 a 192.0.2.6, ligados por oito links ponto a ponto numerados a partir de 198.51.100.0/24, com o mesmo custo nos dois sentidos:

LinkCustoLinkCusto
R1 a R28R3 a R59
R1 a R35R4 a R54
R3 a R23R4 a R66
R2 a R41R5 a R62

O trace do exemplo a partir de R1, calculado em 2026-10-19 com CPython 3.13.16, sem as linhas de links de volta para roteadores já na árvore nem as da lista de candidatos:

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)

No passo 2, R2 custa 8 direto e 8 via R3, então os dois first hops ficam, e tudo atrás de R2 herda o par. No passo 4, R5 cai de 14 para 13: o custo de um candidato ainda pode baixar, o de um roteador já escolhido não. O forwarding usa só o next hop: "only the next hop to the destination is used in the forwarding process", só ele conta para encaminhar (RFC 2328, seção 2.2); como essa entrada disputa a tabela está em tabelas de roteamento e default gateway.

O mesmo cálculo em Python, só com a biblioteca padrão, roda sem mudança no 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

Suba o custo de R2 a R4 de 1 para 20 e rode de novo:

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

Uma mudança tirou R4, R5 e R6 do first hop R2 e acabou com a divisão por custo igual, e todos os roteadores da área recalculam com o mapa novo.

Por que os custos precisam ser positivos

A regra de que o candidato mais próximo é definitivo só vale se nenhum link puder encurtar um caminho. A Memorial Resolution enuncia o problema com "non-negative length", comprimento não negativo (seção 1). Os protocolos proíbem também o zero: "The cost of an interface must be greater than zero", custo maior que zero (RFC 2328, seção 9), e o rascunho de 1990 da norma do IS-IS diz "The path computation algorithm utilised in this International Standard requires that all circuits be assigned a positive value for a metric", métrica positiva em todo circuito (RFC 1142, seção 7.2.2).

A terceira execução do exemplo mostra o motivo. Com links direcionais S para A custo 2, S para B custo 5 e B para A custo menos 4, o Dijkstra fixa A em 2 na primeira rodada; o relaxamento exaustivo acha S, B, A com custo 1. O nó virou definitivo antes que o link negativo pudesse baixar o custo.

O custo viaja na link-state advertisement () do roteador. O FRRouting (FRR) define esse valor com ip ospf cost (1-65535), que grava a métrica da router-LSA usada pelo SPF (FRRouting, OSPFv2). Com custo derivado da banda, a referência padrão do FRR, 100 Mbit/s, dá custo 1 a todo link dessa velocidade ou mais; o guia de OSPF trata das consequências.

O que as normas exigem e o que deixam em aberto

O OSPF calcula em duas etapas: "Using the Dijkstra algorithm, a tree is formed from this subset of the link state database", a árvore dos links entre roteadores e redes de trânsito; as redes stub entram depois como folhas (RFC 2328, seção 16.1). O método não é obrigatório: "if another algorithm is used, an identical tree must be produced", outro algoritmo tem de dar a mesma árvore, e a RFC aponta um SPF incremental de um relatório de 1978 de McQuillan, Richer e Rosen (seção 16.1). O OSPF para IPv6 faz o cálculo sobre o mesmo grafo para IPv4 e IPv6 (RFC 5340, seção 4.8.1).

O IS-IS para IP é "a dynamic routing protocol, based on the SPF (Dijkstra) routing algorithm", baseado no SPF (RFC 1195, seção 1.1), e o anexo dá o custo em palavras: "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", quadrado do número de nós, ou links vezes o log dos nós em redes esparsas (anexo C.1). A Memorial Resolution mede o ganho de 1959 do mesmo jeito: os algoritmos anteriores levavam tempo cúbico no tamanho da rede, o de Dijkstra, quadrático (seção 1). A RFC 1142 aparece aqui só como esse rascunho, que a RFC 7142 declara de interesse apenas histórico (RFC 7142, seção 1). A diferença entre link-state e as outras famílias está em roteamento dinâmico comparado.

Quando o mapa está errado ou não para de mudar

Rotas consistentes exigem bancos de dados idênticos em todos os roteadores (RFC 1142, seção 7.2.6), e o OSPF exige que qualquer algoritmo produza a mesma árvore (RFC 2328, seção 16.1). Entradas velhas ou de mão única ficam de fora: "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", LSA ausente, vencida ou sem link de volta é pulada (seção 16.1). Uma LSA forjada ataca o mapa, não o algoritmo; autenticação é assunto do guia de OSPF. Nem todos os caminhos de custo igual são garantidos: "There is no requirement that a router running OSPF keep track of all possible equal-cost routes to a destination", o roteador não precisa guardar todas (seção 16.8).

Numa rede instável, com falhas múltiplas, convém rodar menos SPF, mas "it's not possible to ensure that all routers trigger their SPF computation after the same delay", não há como igualar a espera de todos, e atrasos desiguais deixam os micro-loops mais prováveis e mais longos (RFC 8405, seção 1). O back-off padronizado passa por três estados, QUIET, SHORT_WAIT e LONG_WAIT (seção 5.2), com valores padrão sugeridos de 50 ms de atraso inicial, 200 ms de atraso curto, 5000 ms de atraso longo, 500 ms de tempo para aprender e 10000 ms de hold-down (seção 6).

O OSPF do FRR tem um hold time adaptativo próprio, e as páginas do projeto não dizem que ele implementa a RFC 8405. timers throttle spf 200 400 10000 define um atraso de 200 ms, um hold time inicial de 400 ms e um máximo de 10 s, e cada evento dentro do hold time atual o aumenta no valor do hold time inicial, até o máximo (FRRouting, OSPFv2). O IS-IS do FRR define um intervalo mínimo, em segundos, com spf-interval [level-1 | level-2] (1-120) (FRRouting, IS-IS). Para o FRR, o cálculo em si pesa pouco nos processadores embarcados modernos, mesmo com milhares de nós (OSPFv2). A detecção rápida de falhas, que dispara essas execuções, é o tema de Bidirectional Forwarding Detection (BFD).

Como ver

No FRR, com a sintaxe que a documentação dá:

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

O primeiro mostra a tabela do OSPF segundo o último SPF (FRRouting, OSPFv2); o segundo imprime "the spf tree from the recent spf calculation with the calling router as the root", a árvore com o próprio roteador na raiz (FRRouting, OSPFv3); o terceiro é a tabela do IS-IS da última execução (FRRouting, IS-IS); o último mostra o hold time atual como múltiplo do inicial (OSPFv2). Num laboratório, compare a saída deles com a do script na mesma topologia.

O outro Dijkstra

"When I came back from Munich, it was September, and I was Professor of Mathematics at the Eindhoven University of Technology", em setembro de 1962 ele era professor em Eindhoven; virou Burroughs Research Fellow em 1º de agosto de 1973 e se mudou para Austin, no Texas, no verão de 1984 (EWD1166). O mesmo texto lembra que ele "thought about synchronizing primitives and designed 'semaphores' for that purpose", os semáforos, e que "for therapeutic reasons I wrote 'Notes on Structured Programming'", escritas por razões terapêuticas. Deixou de dar aulas em novembro de 1999 (Memorial Resolution, seção 4) e morreu em casa, em Nuenen, em 6 de agosto de 2002 (obituário do departamento de Computer Sciences).

O Prêmio Turing de 1972 veio "For fundamental contributions to programming as a high, intellectual challenge", a programação como desafio intelectual, e pela "eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness", programas escritos corretos, não depurados até acertar (ACM). A frase dele sobre testes é de 1970: "Program testing can be used to show the presence of bugs, but never to show their absence", teste mostra bugs, nunca a ausência deles (EWD249, página EWD249-7); não existe código perfeito leva o argumento para a segurança. Suas notas numeradas, os EWDs, chegaram ao número 1318 até a morte dele (Memorial Resolution, seção 6).

Para lembrar

  • Dijkstra criou o algoritmo em 1956 para demonstrar o ARMAC, no terraço de um café em Amsterdã, em uns vinte minutos e sem lápis e sem papel.
  • O artigo de 1959, três páginas na Numerische Mathematik, resolve dois problemas: a árvore geradora mínima e o caminho mais curto.
  • Tudo se apoia numa garantia: o candidato mais próximo da raiz já tem custo definitivo.
  • A RFC 2328 cita o algoritmo de Dijkstra pelo nome, mas exige só uma árvore idêntica; um SPF incremental é permitido.
  • A garantia exige custos não negativos, e OSPF e IS-IS exigem custos maiores que zero.
  • Custos iguais mantêm vários first hops, e uma única mudança de métrica pode mover muitos destinos de uma vez.
  • Em redes instáveis os roteadores atrasam o SPF de propósito: a RFC 8405 padroniza um back-off, e o OSPF do FRR usa um hold time adaptativo próprio.

Fontes