Grafos: Caminhos Mínimos

Metáfora e Motivação

O problema de “Shortest Path” busca a rota de menor custo acumulado entre vértices. O algoritmo ideal depende das propriedades das arestas (pesos positivos, negativos, unitários).

Principais Algoritmos

BFS: Apenas para arestas sem peso (peso 1). \(O(V+E)\).
Dijkstra: Para arestas com pesos não-negativos.
- Usa uma abordagem gulosa com Fila de Prioridade (Heap). Expande sempre o nó mais próximo não visitado.
- Complexidade: \(O(E \log V)\).
Bellman-Ford: Aceita pesos negativos.
- Relaxa todas as arestas \(V-1\) vezes. Se relaxar mais uma vez e melhorar, existe um ciclo negativo.
- Complexidade: \(O(V \cdot E)\).
Floyd-Warshall: Caminho mínimo entre todos os pares.
- Programação Dinâmica \(O(V^3)\). Só para grafos pequenos (\(V \le 400\)).

Problema Clássico

Problema: Países em Guerra (Dijkstra) Link: Beecrowd 1148

Descrição: Calcular o tempo mínimo para enviar cartas entre cidades. Se houver acordo de paz (arestas bidirecionais entre dois países), o custo é zero. Caso contrário, é o peso da aresta.

Solução: Construir o grafo. Se existe \(A \to B\) e \(B \to A\), ajustar pesos. Rodar Dijkstra para cada consulta (K consultas).

Exercício Prático Guiado

Implemente o algoritmo de Dijkstra com fila de prioridade.
Use-o para resolver um problema simples de rotas (como o 1148).
Em seguida, teste sua solução com casos que teriam problemas se houvesse pesos negativos, justificando por que Dijkstra não serve nesses casos.

Variações e Exercícios

[Rota de Entrega]
- Foco: Aplicação direta de Dijkstra ou variação parando no destino.
- Link: Beecrowd 2372 (Reunião - Floyd-Warshall, pois busca o melhor ponto de encontro entre todos).
[Desvio de Rota]
- Foco: Dijkstra modificado ou com estados extras nos nós.
- Link: Beecrowd 1123 (Dijkstra em grafo restrito).
[Caminho com Ciclo Negativo]
- Foco: Detectar wormholes que voltam no tempo (Bellman-Ford).
- Link: Buscar “Wormholes” em UVa ou similares.