Caminho mínimo: Dijkstra com fila de prioridade

Caminho mínimo: Dijkstra

Em um grafo com pesos, o caminho mínimo entre dois vértices é o que soma o menor peso. Se os pesos são distâncias, é o caminho mais curto; se são tempos ou custos, o mais barato.

Ideia do Dijkstra

O algoritmo mantém, para cada vértice, a melhor distância conhecida até a origem, começando com 0 na origem e infinito nos demais. A cada passo, ele retira da fila de prioridade o vértice com a menor distância provisória. Essa distância passa a ser definitiva, porque nenhum caminho futuro pode ser menor (os pesos não são negativos). Depois, ele tenta relaxar as arestas que saem desse vértice: se passar por ele melhora a distância de um vizinho, a distância e o predecessor desse vizinho são atualizados e o vizinho entra na fila.

A fila de prioridade é o que faz o algoritmo rápido. Na animação, ela aparece com os pares (vértice, distância provisória) em ordem de saída.

Por que pesos negativos quebram o método

Com um peso negativo, um vértice já finalizado poderia ser melhorado depois por um caminho que passa por uma aresta negativa. Por isso o Dijkstra recusa grafos com peso negativo. O Bellman-Ford resolve o caso geral: relaxa todas as arestas n − 1 vezes. Se ainda houver relaxamento depois disso, existe um ciclo de peso negativo alcançável, e então a distância mínima não existe (dá para ficar descendo sem limite).

Como ler o resultado

• As distâncias mostradas durante a animação são provisórias, exceto as dos vértices já finalizados.
• O caminho é reconstruído seguindo os predecessores do destino até a origem.
• Ao fim, todas as distâncias alcançáveis são definitivas e os vértices inalcançáveis ficam sem distância.