Algoritmo de Dijkstra — caminho mínimo passo a passo

O algoritmo de Dijkstra encontra caminhos mínimos a partir de um nó inicial em um grafo ponderado, desde que todo peso de aresta seja não negativo. Se você só se importa com um destino, pode parar assim que esse destino for fechado.

A ideia central é gulosa: sempre continuar a partir do nó ainda não fechado com a menor distância conhecida. Isso só funciona sob a condição de pesos não negativos.

O que o algoritmo de Dijkstra resolve

Use o algoritmo de Dijkstra quando você tem um grafo com custos nas arestas e quer a rota mais barata. O custo pode representar distância, tempo de viagem, energia ou alguma outra quantidade que você queira minimizar.

Ele funciona em grafos direcionados ou não direcionados. A condição principal é explícita: todo peso de aresta deve ser pelo menos $0$.

Como o algoritmo funciona

Cada nó mantém uma distância provisória a partir do nó inicial. No começo, o nó inicial tem distância $0$ e todos os outros nós têm distância $\infty$.

Depois, repita este ciclo:

1. Escolha o nó ainda não fechado com a menor distância provisória.
2. Verifique cada vizinho por meio desse nó.
3. Se a nova rota for mais barata, atualize a distância do vizinho.
4. Marque o nó atual como fechado.

O passo 3 é chamado de relaxamento. Um nó fechado está concluído: sua menor distância é final, desde que o grafo não tenha arestas com peso negativo.

Algoritmo de Dijkstra passo a passo

Aqui está o procedimento completo de forma compacta:

1. Escolha um nó inicial.
2. Defina sua distância como $0$ e todas as outras distâncias como $\infty$.
3. Selecione o nó ainda não fechado com a menor distância provisória.
4. Relaxe suas arestas de saída.
5. Marque esse nó como fechado.
6. Repita até que todos os nós alcançáveis estejam fechados, ou pare quando o nó de destino for fechado.

Se você também armazenar qual nó anterior causou cada atualização, poderá recuperar o caminho real, e não apenas a distância final.

Exemplo resolvido de caminho mínimo

Suponha que o grafo tenha estes pesos nas arestas:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Queremos o caminho mínimo de $A$ até $D$.

Comece com:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Feche $A$ primeiro e relaxe suas arestas:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

A menor distância ainda não fechada agora está em $C$, então feche $C$ em seguida.

Passando por $C$:

• Por $C$, o caminho até $B$ custa $1+2=3$, o que melhora $4$, então atualize $\text{dist}(B)=3$.
• Por $C$, o caminho até $D$ custa $1+5=6$, então defina $\text{dist}(D)=6$.

Agora $B$ tem a menor distância ainda não fechada, então feche $B$.

Passando por $B$, o caminho até $D$ custa:

$$3+1=4$$

Isso melhora $6$, então atualize $\text{dist}(D)$ de $6$ para $4$.

Agora $D$ é o nó ainda não fechado com a menor distância. Feche-o e pare.

O caminho mínimo é:

$$A \to C \to B \to D$$

com custo total:

$$1+2+1=4$$

Este exemplo mostra o padrão principal: uma rota que no início parecia pior, $A \to B$, depois ficou melhor por meio de $C$. O algoritmo de Dijkstra permite isso enquanto $B$ ainda não foi fechado. Depois que um nó é fechado, sua distância não muda mais.

Por que pesos não negativos importam

Suponha que o nó ainda não fechado mais barato no momento tenha distância $d$. Qualquer novo caminho até esse nó encontrado depois teria de vir de outro nó ainda não fechado cuja distância provisória é pelo menos $d$, e então somar uma aresta de peso pelo menos $0$.

Portanto, essa rota posterior não pode ser melhor que $d$. É por isso que fechar a menor distância provisória é seguro quando todos os pesos são não negativos.

Se existir uma aresta negativa, esse argumento falha. Um caminho que agora parece caro pode ficar mais barato depois, o que significa que fechar um nó cedo demais pode dar a resposta errada.

Erros comuns com o algoritmo de Dijkstra

Usá-lo com uma aresta negativa

Mesmo uma única aresta negativa pode quebrar a lógica gulosa. Se pesos negativos forem possíveis, use outro método de caminho mínimo.

Tratar "visto" como "concluído"

Um nó já pode ter uma distância provisória e ainda assim não estar concluído. Só um nó fechado tem uma menor distância final.

Esquecer a tabela de nós anteriores

As distâncias dizem o custo. Se você também quiser a rota em si, armazene qual nó foi o último a melhorar cada distância.

Onde o algoritmo de Dijkstra é usado

O algoritmo de Dijkstra é usado quando um problema pode ser modelado como movimento em um grafo com custos não negativos:

• Planejamento de rotas em mapas
• Roteamento de redes
• Movimento de robôs em grades ponderadas
• Pathfinding em jogos quando os custos de movimento variam

Ele também é um exemplo clássico de algoritmo guloso cuja correção depende de uma condição precisa.

Tente um problema parecido

Desenhe um grafo com cinco nós e pesos de aresta positivos, depois execute o algoritmo de Dijkstra à mão com uma tabela de distâncias. Se quiser um bom próximo passo, tente sua própria versão em um novo grafo e verifique exatamente quando cada nó se torna seguro para ser fechado.