Algoritmo de Dijkstra
Encontra o caminho mais barato de um início até um destino. Tira sempre o lugar mais barato que espera numa fila de prioridade, por isso os custos espalham-se a partir do início como uma cheia.
- tempo O((V + E) log V)
- memória O(V)
- usa uma fila de prioridade
O que significam estes termos?
- Custo: quanto custa um movimento. No labirinto, pisar o chão custa 1, a lama 3 e a água 9; no grafo, é o número na aresta.
- Fila de prioridade: uma fila onde passa primeiro o mais barato, não quem chegou primeiro.
- Estimativa (h): uma previsão do custo que falta. O A* só se mantém exato se ela nunca for alta demais.
- Relaxar uma aresta: verificar se passar pelo lugar atual dá a um vizinho um custo mais baixo e, se der, ficar com ele.
- na fila
- atual
- terminado
- caminho mais barato
- chão · 1
- lama · 3
- água · 9
- parede
Novo: Início em A1 com custo 0. É o único na fila.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: saltar.
Experimente: Escolha o pântano. O caminho mais barato contorna toda a lama: o dobro dos movimentos da linha reta e, ainda assim, mais barato (34 contra 36).
Como funciona
Cada lugar recebe um custo: 0 para o início, infinito para o resto. O Dijkstra guarda os lugares alcançados numa fila de prioridade e tira sempre o mais barato. Esse custo fica então definitivo, porque qualquer outro caminho teria de passar por algo pelo menos tão caro. Depois olha para cada vizinho: se passar pelo lugar que acabou de tirar for mais barato do que o custo atual do vizinho, o vizinho recebe o novo custo e guarda de onde veio. Quando o destino é tirado, esses registos levam de volta pelo caminho mais barato.
Quando é uma boa escolha
Use o Dijkstra quando os movimentos custam valores diferentes e nenhum custa menos de zero: mapas de estradas e GPS, encaminhamento em redes, a combinação de voos mais barata. Se todos os movimentos custam o mesmo, a BFS dá a mesma resposta de forma mais simples. Com custos negativos o Dijkstra pode falhar; para isso existe o Bellman-Ford.