Grafos: Caminhos Mínimos

Introdução Teórica

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

  1. BFS: Apenas para arestas sem peso (peso 1). \(O(V+E)\).
  2. 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)\).
  3. 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)\).
  4. 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).

Variações e Exercícios

  1. [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).
  2. [Desvio de Rota]
    • Foco: Dijkstra modificado ou com estados extras nos nós.
    • Link: Beecrowd 1123 (Dijkstra em grafo restrito).
  3. [Caminho com Ciclo Negativo]
    • Foco: Detectar wormholes que voltam no tempo (Bellman-Ford).
    • Link: Buscar “Wormholes” em UVa ou similares.
Back to top