Por que um site de redes lhe deve um artigo

Abra a tabela de roteamento de quase qualquer rede corporativa e algo no caminho foi decidido por um algoritmo publicado em 1959, num artigo de duas páginas, por um holandês que ainda não terminara o doutorado.

Protocolos de roteamento por estado de enlace funcionam dando a todo roteador o mesmo mapa: cada um inunda a rede com a descrição dos próprios enlaces, todos montam um retrato idêntico da rede, e então cada roteador calcula de forma independente o melhor caminho de si mesmo até todo o resto. Esse último passo - o cálculo - é o algoritmo do caminho mais curto de Dijkstra, e é por isso que o processo se chama , shortest path first - o nome sobrevive em , Open Shortest Path First - e por que o primer de OSPF e o primer de IS-IS citam o nome dele de passagem. Este artigo é a parte que os dois deixam de fora.

O café

Edsger Wybe Dijkstra nasceu em Roterdã em 1930 e estudou física teórica em Leiden, formando-se em 1956. Trabalhava no Centro Matemático de Amsterdã, que acabara de construir um computador novo chamado ARMAC e queria demonstrá-lo publicamente.

Essa é a origem do algoritmo, e merece ênfase porque inverte a história de sempre sobre matemática difícil. Dijkstra não estava resolvendo um problema de roteamento. Ele precisava de uma demonstração que não especialistas conseguissem acompanhar. Nas palavras dele, para uma demonstração a pessoas de fora da computação é preciso ter um enunciado de problema que não matemáticos entendam - e eles têm de conseguir entender a resposta também. Então escolheu o caminho mais curto entre duas cidades holandesas, num mapa reduzido com sessenta e quatro delas, sessenta e quatro porque seis bits bastam para identificar uma.

A resolução aconteceu em outro lugar. O relato dele, dado numa entrevista décadas depois, é uma das passagens mais citadas da computação:

Numa manhã eu estava fazendo compras em Amsterdã com minha jovem noiva e, cansados, sentamos no terraço de um café para tomar um café, e eu estava justamente pensando se conseguiria fazer isso, e então projetei o algoritmo do caminho mais curto. Como eu disse, foi uma invenção de vinte minutos.

Sem caneta. Sem papel. Ele observou depois que projetar sem eles teve uma vantagem, no que a ausência lhe impôs.

A história costuma ser contada como a de um homem ignorando a noiva para pensar em matemática, o que é injusto e menos interessante que a verdade. Ria Debets era programadora. Era uma de cerca de doze mulheres que tinham saído da escola com notas excepcionais em matemática e foram contratadas para o novo departamento de computação do Centro Matemático - e Dijkstra ensinara a ela e às colegas a programar. Casaram-se cerca de um ano depois e ficaram juntos até a morte dele, em 2002.

Ele não se deu ao trabalho de publicar por três anos, e só o fez porque alguém disse que devia. A Note on Two Problems in Connexion with Graphs saiu na Numerische Mathematik em 1959 e tem umas duas páginas. O caminho mais curto está na segunda metade; a primeira é outro algoritmo, igualmente duradouro, para a árvore geradora mínima. Ele soube que a coisa tinha nome ao vê-la num livro alemão de ciência da administração em 1960, como Das Dijkstra'sche Verfahren.

O que o algoritmo de fato faz

Vale enunciar sem rodeios, porque é mais simples que a reputação.

Você quer a rota mais barata de onde está até todo o resto, num mapa em que cada estrada tem um custo. Mantenha um melhor custo conhecido até cada lugar, começando em zero para onde você está e desconhecido para todo o resto. Então repita um passo: pegue o lugar não visitado de menor custo conhecido, marque-o como visitado, e para cada vizinho dele veja se ir por ali sai mais barato que o melhor que você tinha. Se sair, anote o número melhor. Pare quando não houver mais nada a visitar.

É só isso. A sacada - a parte que levou vinte minutos e não é óbvia - é que, uma vez que você pega o lugar não visitado mais barato, o custo dele é final. Nada que você descubra depois pode melhorá-lo, porque qualquer outra rota até ele teria de passar antes por algum lugar mais caro. Essa única garantia é a razão de o procedimento terminar com respostas corretas em vez de precisar reconsiderar tudo, e é por isso que um roteador calcula uma topologia inteira em milissegundos em vez de tentar todos os caminhos possíveis.

Ela também explica uma restrição prática que pega gente desprevenida: a garantia depende de os custos nunca serem negativos. Um enlace não pode ter métrica negativa, e isso não é restrição arbitrária de fabricante.

O outro Dijkstra

O algoritmo é sua contribuição mais usada e provavelmente não a mais importante. Ele passou o resto de uma longa carreira - Eindhoven a partir de 1963, uma bolsa de pesquisa na Burroughs, depois a Universidade do Texas em Austin até 2000 - argumentando, longamente e com enorme segurança de estilo, que programar deveria ser uma disciplina matemática e não um ofício de tentativa e erro.

Ele deu ao campo a programação estruturada. Deu os semáforos e o vocabulário dos processos concorrentes. E deu o hábito, em boa parte perdido, de raciocinar sobre se um programa está correto em vez de rodá-lo para ver. Sua frase mais citada sobre o assunto pertence a qualquer discussão sobre testes: o teste de programas pode ser usado para mostrar a presença de defeitos, nunca para mostrar sua ausência. Não é floreio retórico; é uma afirmação sobre que evidência um teste fornece, e o argumento de que não existe código perfeito deste site é uma reformulação dela cinquenta anos depois.

Ele escreveu mais de mil manuscritos numerados - a série EWD - à mão, com caneta-tinteiro, e fazia circular fotocópias entre colegas que as faziam circular mais. Era um samizdat privado de opinião técnica, e fez dele a pessoa mais citada e mais contestada de sua área.

O que um profissional deve tirar disso

O algoritmo mais usado em redes foi projetado como material didático. Existe porque alguém precisava explicar uma máquina a pessoas que não entendiam de máquinas, e decidiu que o jeito era escolher um problema e uma resposta que elas entendessem. Quem ensina assuntos técnicos deveria parar um instante nisso. A obrigação de ser compreensível não enfraqueceu o resultado; ela o produziu.

Restrições ao pensamento podem ser produtivas. Sem caneta, sem papel, vinte minutos, e o resultado foi pequeno o bastante para estar correto e continuar rodando setenta anos depois. O próprio Dijkstra achava que a ausência de material de escrita era parte da razão de ele ter saído limpo.

E o algoritmo tem um formato que cabe na cabeça. Pegue a coisa não visitada mais próxima; o custo dela agora é final; atualize os vizinhos; repita. Quando uma adjacência OSPF sobe e a topologia é recalculada, é isso que está acontecendo - e quem sabe disso consegue raciocinar sobre por que uma mudança de métrica teve o efeito que teve, em vez de tratar a tabela de roteamento como um oráculo.

Fontes