Caminhos Mínimos

Um caminho mínimo minimiza a soma dos pesos das arestas. O algoritmo correto depende principalmente do modelo de pesos.

Guia de seleção

Pesos / consulta	Algoritmo
Sem pesos	BFS
Apenas 0 ou 1	BFS 0–1 com deque
Não negativos	Dijkstra
Arestas negativas permitidas	Bellman–Ford
Todos os pares de vértices, grafo moderadamente denso	Floyd–Warshall
Direcionada ao objetivo com heurística admissível	A*

Algoritmo de Dijkstra

Mantenha distâncias provisórias e finalize repetidamente, com uma fila de prioridade, o vértice não resolvido que possui distância mínima. Relaxar u → v testa se distance[u] + weight(u,v) melhora distance[v].

A etapa gulosa é segura porque toda continuação ainda não explorada tem custo não negativo. Uma aresta negativa pode revelar uma rota mais barata depois que um vértice foi considerado definitivo, invalidando a prova.

Com listas de adjacências e um heap binário, uma implementação comum leva tempo O((V + E) log V) e armazenamento O(V + E) para o grafo e o trabalho. Filas de prioridade Java normalmente tratam uma redução de distância inserindo uma nova entrada e descartando entradas obsoletas ao removê-las.

Bellman–Ford

Relaxe cada aresta V - 1 vezes. Todo caminho mínimo simples possui no máximo V - 1 arestas. Um relaxamento adicional bem-sucedido identifica um ciclo de peso negativo alcançável a partir da origem; assim, distâncias mínimas finitas ficam indefinidas para vértices alcançáveis por esse ciclo. O tempo é O(VE).

Floyd–Warshall e A*

Floyd–Warshall usa dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) para sucessivos vértices intermediários permitidos, com tempo Θ(V³) e espaço Θ(V²). A* prioriza o custo total estimado; uma heurística admissível preserva a otimalidade, enquanto a consistência simplifica o comportamento da busca em grafos.

Exercícios

1. Dê um grafo em que Dijkstra falhe por causa de uma aresta negativa.
2. Adicione o rastreamento de predecessores e reconstrua um caminho.
3. Explique como o overflow de inteiros pode corromper o relaxamento.