Caminho mais curto de Dijkstra

O algoritmo de Dijkstra encontra o caminho mais curto entre nós num grafo com pesos não negativos. Funciona de forma gananciosa (greedy) e atualiza distâncias por relaxação: d(v) = min(d(v), d(u) + w(u,v)). A complexidade é otimizada para O(E + V log V) usando filas de prioridade com heap de Fibonacci.

O Dijkstra faz crescer uma fronteira a partir do nó inicial e fixa sempre o nó ainda não visitado que está mais perto. Como todo peso de aresta é não negativo, nenhum desvio posterior consegue superar um caminho mais curto já encontrado: uma vez fixado um nó, sua distância é definitiva e nunca é revista. Por isso planejadores de rotas e protocolos de roteamento como o OSPF recorrem a ele para calcular caminhos mínimos confiáveis.

Edsger Dijkstra concebeu o algoritmo em 1956 em cerca de vinte minutos, sem lápis nem papel, enquanto descansava no terraço de um café em Amsterdã. Ele procurava um problema de demonstração para o computador ARMAC e escolheu a rota mais curta entre duas cidades neerlandesas, Roterdã e Groningen. Publicou-o três anos depois num artigo de apenas três páginas, um dos resultados mais citados da computação.