Algoritmo de Dijkstra
Encontra o caminho mais barato de um início até uma meta. Sempre pega o lugar mais barato que espera numa fila de prioridade, então os custos se espalham a partir do início como uma enchente.
- tempo O((V + E) log V)
- memória O(V)
- usa uma fila de prioridade
O que significam esses termos?
- Custo: quanto custa um movimento. No labirinto, pisar no chão custa 1, na lama 3 e na água 9; no grafo, é o número na aresta.
- Fila de prioridade: uma fila em que passa primeiro o mais barato, não quem chegou antes.
- Estimativa (h): um palpite do custo que falta. O A* só continua exato se ela nunca for alta demais.
- Relaxar uma aresta: conferir se passar pelo lugar atual dá a um vizinho um custo menor e, se der, ficar com ele.
- na fila
- atual
- pronto
- 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: pular.
Experimente: Escolha o pântano. O caminho mais barato contorna toda a lama: o dobro de movimentos da linha reta e, mesmo assim, mais barato (34 contra 36).
Como funciona
Cada lugar recebe um custo: 0 para o início, infinito para o resto. Dijkstra guarda os lugares alcançados numa fila de prioridade e sempre pega o mais barato. Esse custo passa a ser definitivo, porque qualquer outro caminho teria de passar por algo pelo menos tão caro. Depois ele olha cada vizinho: se passar pelo lugar que acabou de pegar sai mais barato que o custo atual do vizinho, o vizinho recebe o novo custo e guarda de onde veio. Quando a meta é pega, esses registros levam de volta pelo caminho mais barato.
Quando é uma boa escolha
Use Dijkstra quando os movimentos custam valores diferentes e nenhum custa menos que zero: mapas de estradas e GPS, roteamento de redes, a combinação de voos mais barata. Se todo movimento custa o mesmo, BFS dá a mesma resposta de forma mais simples. Com custos negativos Dijkstra pode errar; para isso existe Bellman-Ford.