← Computação

Caminho mais curto de Dijkstra

Veja como o algoritmo de Dijkstra encontra o caminho mais curto em um grafo ponderado.

A carregar a simulação interativa...

A relaxação é o algoritmo todo; a fila de prioridade é apenas velocidade

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.

Por que o nó mais próximo é seguro

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.

Concebido em vinte minutos com um café

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.

Problema resolvido na íntegra

  1. O nó 1 a uma aresta da origem com um custo de 4 5 passos

    O nó 1 está a uma aresta da origem, com um custo de 4 — e o algoritmo indica a sua distância como sendo 3. Percorra a ordem de fixação e descubra de onde vem o 3.

    1. O algoritmo de Dijkstra fixa os nós por ordem de distância, sem nunca os revisitar. Essa ordenação é todo o algoritmo e toda a demonstração: quando um nó é fixado, não pode existir nenhum percurso mais barato até ele, pois qualquer percurso desse tipo teria de passar por um nó não fixado que já se encontra mais distante.

      E={(0,1,4),(0,3,2),(1,2,5),(1,3,1),(2,4,3),(3,4,6)}E=\{(0,1,4),(0,3,2),(1,2,5),(1,3,1),(2,4,3),(3,4,6)\}

    2. A partir da origem, as duas arestas diretas dão distâncias provisórias de 4 e 2. Nenhuma é ainda definitiva — são limites superiores.

      settle 0: d1=4, d3=2\text{settle }0:\ d_1=4,\ d_3=2

    3. O mais próximo é o nó 3 com 2, pelo que é o primeiro a ser fixado. O relaxamento das suas arestas encontra um percurso para o nó 1 com um custo de 2 + 1 = 3, o que supera a aresta direta de 4. Este é o passo que responde à pergunta: o caminho mais barato para um vizinho não tem de ser a aresta direta até ele.

      settle 3 (d=2): d1=min⁡(4, 2+1)=3,d4=2+6=8\text{settle }3\ (d=2):\ d_1=\min(4,\,2+1)=3,\quad d_4=2+6=8

    4. O nó 1 é fixado em 3, e o relaxamento a partir daí alcança o nó 2 em 8.

      settle 1 (d=3): d2=3+5=8\text{settle }1\ (d=3):\ d_2=3+5=8

    5. O nó 4 é alcançável em 8 através do nó 3, e a alternativa através do nó 2 custa 8 + 3 = 11, pelo que prevalece o mais curto.

      settle 2,4: d4=min⁡(8, 8+3)=8⟹0→3→4\text{settle }2,4:\ d_4=\min(8,\,8+3)=8\quad\Longrightarrow\quad 0\to3\to4

    Resposta

    A ferramenta apresenta distâncias de 3, 8, 2, 8 e um caminho mais curto de 0 → 3 → 4. A lição está no nó 1: uma aresta direta não é um caminho mais curto, e a fixação ambiciosa é o que torna essa descoberta eficiente em vez de exponencial. A garantia tem, contudo, um requisito — pesos não negativos. Com uma aresta negativa, um nó fixado cedo pode vir a ser melhorado mais tarde, e a demonstração do passo 1 deixa de ser válida. Clique na predefinição de arestas negativas e veja o algoritmo falhar em ambas as direções de uma só vez: o nó 3 surge com −1, que não é uma distância produzida por nenhum percurso, e a reconstrução do caminho desiste por completo com “sem caminho — os predecessores formam um ciclo”. Números errados e nenhum percurso, num algoritmo cuja correção é demonstrada assim que todos os pesos são não negativos.

    d1=3 via node 3, not 4 direct;0→3→4=8d_1=3\ \text{via node 3, not }4\ \text{direct};\quad 0\to3\to4=8
Referências (2)

· Verificado com fontes publicadas. Correções bem-vindas.