Algoritmo de Dijkstra

O seu planeador de rotas conhece o caminho mais rápido da sua porta até quase qualquer lugar. No centro dessa ideia está um algoritmo que Edsger Dijkstra concebeu em cerca de vinte minutos em 1956: crescer para fora a partir da origem e terminar sempre primeiro o lugar mais próximo.

Um grafo cujas arestas têm comprimentos, com os nós perto da origem já terminados a verde, uma árvore de caminhos mais curtos e uma fila de prioridade desenhada por baixo
Um grafo cujas arestas têm comprimentos, com os nós perto da origem já terminados a verde, uma árvore de caminhos mais curtos e uma fila de prioridade desenhada por baixo

A ideia

Imagine cidades ligadas por estradas de comprimentos diferentes. A pergunta é: qual é o caminho mais curto da minha cidade até cada uma das outras? A pesquisa em largura responde quando todas as estradas contam o mesmo, mas aqui um percurso com mais estradas pode ser mais curto. O algoritmo de Dijkstra guarda, para cada cidade, a distância mais curta encontrada até agora, e faz crescer uma região de cidades cuja distância é certa, juntando sempre a cidade mais próxima que ainda não é certa.

Passo a passo

Dê à origem a distância 0 e a todos os outros nós infinito. Coloque a origem numa fila de prioridade, uma fila que entrega sempre o nó com a menor distância. Retire esse nó; a sua distância é agora definitiva. Para cada vizinho que não seja definitivo, calcule a distância passando por este nó: a sua distância mais o comprimento da aresta. Se for menor do que a distância que o vizinho tinha, baixe-a, registe este nó como o caminho até lá e coloque o vizinho na fila. A isto chama-se relaxar uma aresta. Repita até a fila ficar vazia, ou até o destino sair dela.

Um exemplo

Tome as arestas A–B de comprimento 4, A–C 1, B–C 2, B–D 1, C–D 5 e D–E 3, e comece em A. Retirar A dá a B a distância 4 e a C a distância 1. C é o mais próximo, por isso fica definitivo com 1; através de C, B desce para 1 + 2 = 3 e D recebe 1 + 5 = 6. Agora B é o mais próximo, definitivo com 3, e através de B, D desce para 3 + 1 = 4. D fica definitivo com 4 e dá a E 4 + 3 = 7. Assim, o caminho mais curto de A até E é A → C → B → D → E, de comprimento 7, embora A → B → D → E use menos arestas e tenha comprimento 8.

Porque é que está correto

Suponha que o nó X é o mais próximo na fila, à distância d. Qualquer outro caminho da origem até X tem de sair, em algum ponto, da região dos nós definitivos, e o primeiro nó que alcança fora dessa região está na fila, logo já está pelo menos a d. O resto do caminho não o pode encurtar, porque nenhuma aresta é negativa. Portanto, d é a distância mais curta até X. Com uma aresta negativa, este argumento falha; usa-se então o algoritmo de Bellman–Ford, que relaxa todas as arestas uma e outra vez.

História e utilizações

Edsger W. Dijkstra criou o algoritmo em 1956 para mostrar um novo computador, o ARMAC, em Amsterdam, encontrando rotas entre cidades neerlandesas, e publicou-o em 1959. A mesma ideia, com uma fila mais inteligente, funciona nos planeadores de rotas e em protocolos de encaminhamento da internet como o OSPF e o IS-IS, que calculam o caminho mais curto para os dados entre routers. O algoritmo A* acrescenta uma estimativa da distância que falta, para poder dirigir-se ao destino e examinar menos nós.

Edsger W. Dijkstra no quadro
Edsger W. Dijkstra no quadro

Experimente

Abra a aplicação e prima Avançar. Os números nas arestas são os seus comprimentos, e o número em cada nó é a sua distância até agora. Os nós na fila são azuis, os definitivos verdes, e a fila por baixo do grafo lista-os do mais próximo para o mais distante, com as suas distâncias. Repare nos momentos em que uma distância desce porque um percurso que parecia mais longo afinal é mais curto, e escolha um destino para ver a pesquisa parar assim que o destino fica definitivo.

Perguntas frequentes

Qual é a complexidade temporal do algoritmo de Dijkstra?

Depende da fila de prioridade. Com uma lista simples é O(V²) para V nós; com um heap binário, O((V + E) log V) para E arestas; com um heap de Fibonacci, O(E + V log V), como mostraram Michael Fredman e Robert Tarjan em 1984.

O algoritmo de Dijkstra funciona com pesos negativos nas arestas?

Não. Pressupõe que a distância de um nó não pode melhorar depois de o nó ser o mais próximo na fila, e uma aresta negativa pode quebrar isso. Use o algoritmo de Bellman–Ford para grafos com arestas negativas.

O algoritmo de Dijkstra encontra o caminho até cada nó?

Sim. Executado até ao fim, dá a distância mais curta da origem até cada nó alcançável, e os nós registados formam uma árvore de caminhos mais curtos. Parar mais cedo, quando o destino fica definitivo, poupa trabalho quando só é preciso um caminho.

Qual é a relação entre o algoritmo de Dijkstra e o A*?

O algoritmo A* é o algoritmo de Dijkstra com uma pista: ordena a fila pela distância até agora mais uma estimativa da distância que falta, como a distância em linha reta num mapa. Com uma boa estimativa, encontra o mesmo caminho mais curto examinando muito menos nós.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar o algoritmo de Dijkstra