Algoritmos do Menor Caminho
O problema do Caixero Viajante e Algoritmo de Dijkstra
Existem muitos algoritmos para encontrar o menor caminho um grafo. Dois muito populares deles são a implementação da solução do problema do Caixeiro Viajante e o algoritmo de Dijkstra. Mas pra que servem e quais são as diferenças entre os dois?
Primeiramente uma diferença importante: o Caixeiro Viajante é um problema para o qual podem existir muitas soluções e/ou implementações em forma de algoritmo. Já Dijkstra é um algoritmo exato.
A comparação entre os dois se dará pela ótica de qual tipo de problema cada um dos dois procura resolver.
Menor caminho em um grafo
O que quer dizer “menor caminho em um grafo”? Como analogia, vamos pensar no boy dos lanches fazendo entregas pela cidade. A cidade é o grafo e os pontos a serem considerados são a lancheria e as casas.
O Problema do Caixeiro Viajante
Vamos supor que o entregador tenha uma pilha de pizzas a serem entregues em diversas casas e que depois precisa voltar para a lancheria. A solução do problema do Caixeiro Viajante encontra a rota menos custosa para visitar todos os pontos e voltar para o ponto inicial.
Dijkstra
Mas se o entregador só precisa ir até uma casa de uma vez e quer a melhor rota pra isso? Suponhamos que a rota de menor kilometragem não tenha asfalto, ou que esteja congestionada. Dijkstra tem a solução!
Cada parte do caminho (ou cada rua) é considerada e recebe um “peso” e no final a com menor peso total é a escolhida. É tipo aquela dica que você dá pro boy do lanche chegar mais rápido: “pega a perimetral e desce ali pelo Buteco Dois Irmãos que nesse horário chega mais rápido”.
E pra que isso serve?
Além de ser pergunta de FAANG, serve para: otimizar rotas (Caixeiro Viajante) e encontrar o caminho menos custoso entre um ponto e outro (Dijkstra).
Resumo
A solução do problema do Caixeiro Viajante tenta encontrar o menor caminho para visitar todos os pontos e retornar ao ponto de partida.
O algoritmo de Dijkstra considera o peso entre todas as rotas para encontrar o caminho menos custoso de A até B.
Fun fact: Dijkstra era holandês.
Exemplo de implementação para a solução do problema do Caixeiro Viajante:
Implementação de Dijkstra:
