2 - Menor caminho: algoritmo de Dijkstra

O Dijkstra é um dos algoritmos clássicos da área de grafos. Ele é comumente utilizado em situações em que se deseja encontrar o menor caminho de um vértice origem para todos os outros vértices do grafo, mas também pode ser adaptado para encontrar o menor caminho entre dois vértices específicos. Como? É só parar ele no meio do caminho.

O algoritmo é baseado nas técnicas de programação dinâmica para obter uma boa performance. Calma, eu não vou explicar em detalhes o que é programação dinâmica, isso em si daria uma disciplina de 60 horas do curso! A ideia bem simplificada (mas olhe, é BEM simplificada) é salvar e reutilizar resultados que você já encontrou uma vez na execução do algoritmo, para não ter de calcular de novo. O algoritmo vai “lembrando” dos resultados e, quando precisa de algo que ele já sabe, por exemplo, o custo para chegar em um vértice que ele já calculou não precisa refazer as contas, apenas usa o que já está armazenado. A ideia é simples, a implementação não.

Uma característica interessante desse algoritmo é que ele testa vários caminhos até cada vértice, mas salva apenas o menor que foi encontrado ao longo da execução. Por exemplo, para um vértice X, se ele salva o menor custo de chegar a X, então todos os caminhos que passam por X usarão esse custo. Ele não precisa ficar recalculando esse valor toda vez que encontrar um caminho que passa por X, ele apenas utiliza o que já foi calculado anteriormente. No Código 01 pode-se ver o pseudocódigo do algoritmo.

É difícil visualizar como ele funciona, não é mesmo? Imagine como se fosse uma busca sistemática, só que ela vai salvando os valores do caminho encontrado, e não precisa retornar em nenhum momento. É quase como se o caminho fosse uma “onda” que vai varrendo os vértices do grafo e atualizando com os menores caminhos possíveis, até chegar ao ponto de origem. Veja um exemplo com o mapa da seção anterior em que você partirá do mesmo ponto.

Assuma que o custo de movimentação entre os blocos é 1, e não há diferença entre movimento vertical e horizontal (da mesma forma que foi feito no exemplo anterior):

Foi processado o primeiro vértice (origem, marcado de verde) e atualizadas as distâncias dos vizinhos a partir dele. Esse processo será repetido até chegar no vértice destino.

Os vértices visitados passam a ser coloridos de vermelho e não serão mais explorados (o valor contido já é o menor caminho possível até ele). O vértice atual em exploração continua marcado como verde.

A partir de agora, eu vou “queimar” algumas etapas na sequência senão o pessoal que faz as imagens vai desmaiar de exaustão! Você verá a exploração de vários vértices simultaneamente, mas a ideia é repetir o processo de um por um. Dessa forma tem-se garantia de o caminho até o vértice será sempre o menor!

Todos os vértices em uma distância de 3 que tem vizinhos.

Todos os vértices que percorreram uma distância de 4 casas.

Todos os vértices que percorreram uma distância de 5.

Ao explorar todos os vértices que percorreram uma distância de 6, você encontrará um que chega até o destino. Como todas as distâncias são unitárias, tem-se a garantia de que esse primeiro que chegou é o menor caminho, que seguindo o algoritmo pode ser expresso pelo seguinte desenho:

Perceba que existem mais dois caminhos que possuem o mesmo custo: o que passa por (4,2) e o que passa por (5,2). Qualquer um desses três caminhos satisfazem a condição de ser o menor caminho entre o bloco (4,1) e o bloco (4,8).

Para esse mapa do exemplo, não é possível ver tanta vantagem no algoritmo de Dijkstra frente às outras buscas. Porém, quando o cenário começa a ficar mais complexo, ele torna-se mais eficaz do que as buscas para a solução do caminho:

• Mapas com custos distintos de movimentação (por exemplo, terrenos diferentes);
• Mapas com layout mais intrincado, cheios de obstáculos.

Mesmo assim, esse algoritmo ainda precisa visitar um grande número de vértices para achar a resposta correta. Sem entrar em muitos detalhes de complexidade de algoritmos, suponha que, se o seu mapa tiver 5000 blocos, ele ainda quebra bem o galho. Mas em um mapa com 1.000.000 de blocos, aí os seus caminhos iam demorar muito tempo para serem calculados! E não é difícil pensar mapas grandes, dado o tamanho de alguns cenários em jogos atuais! Por esse motivo, o algoritmo de Dijkstra tradicional não é tão usado para achar o caminho entre dois pontos, mas sim uma otimização que foi criada a partir dele: o algoritmo A*.