Caminhos Mínimos: Bellman-Ford e Floyd-Warshall

1. Quando o Dijkstra falha?

Se um grafo tem arestas com pesos negativos, o Dijkstra não funciona. Pesos negativos aparecem em: - Finanças (Arbitragem de moedas). - Química (Reações que liberam energia). - Física e Redes de Fluxo (grafos residuais).

Se houver um Ciclo Negativo (uma volta no grafo que diminui o custo total), não existe “menor caminho” (podemos ficar girando para sempre e chegar em \(-\infty\)).

2. Algoritmo de Bellman-Ford

Criado por Richard Bellman (pai da Programação Dinâmica) e Lester Ford. Resolve o problema de Single Source Shortest Path mesmo com pesos negativos e detecta ciclos negativos.

Lógica (\(V - 1\) Iterações)

O menor caminho simples não pode ter mais que \(V-1\) arestas. 1. Inicialize dist[S] = 0, dist[rest] = ∞. 2. Repita \(V-1\) vezes: - Itere por todas as arestas \(E\). - Tente relaxar cada aresta. 3. Se na iteração \(V\) ainda for possível relaxar algo, então existe um Ciclo Negativo.

Implementação Java (Edge List)

class Aresta { int u, v, w; ... }

public void bellmanFord(int V, int start, List<Aresta> arestas) {
    int[] dist = new int[V];
    Arrays.fill(dist, 9999999); // Infinito seguro (evita overflow na soma)
    dist[start] = 0;
    
    // Passo 1: Relaxar V-1 vezes
    for (int i = 0; i < V - 1; i++) {
        for (Aresta e : arestas) {
            if (dist[e.u] != 9999999 && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }
    
    // Passo 2: Detectar Ciclo Negativo
    for (Aresta e : arestas) {
         if (dist[e.u] != 9999999 && dist[e.u] + e.w < dist[e.v]) {
             System.out.println("Erro: Ciclo Negativo Detectado!");
             return;
         }
    }
}

Complexidade: \(O(V \times E)\). Lento para grafos grandes.

3. Algoritmo de Floyd-Warshall

O Floyd-Warshall resolve um problema diferente: All-Pairs Shortest Path. Queremos a matriz de distâncias de todos para todos.

Ele usa Programação Dinâmica. A ideia é testar gradualmente se passar por um vértice intermediário \(k\) melhora o caminho entre \(i\) e \(j\).

Algoritmo

  1. Crie uma matriz \(D[V][V]\).
    • \(D[i][i] = 0\).
    • \(D[i][j] = peso(i, j)\) se existe aresta.
    • \(D[i][j] = \infty\) caso contrário.
  2. Três loops aninhados (A ordem \(k, i, j\) é crucial! \(k\) deve ser o mais externo).

Implementação Java

public void floydWarshall(int V, int[][] grafo) {
    int[][] dist = new int[V][V];
    
    // Cópia inicial
    for(int i=0; i<V; i++) 
        for(int j=0; j<V; j++) 
            dist[i][j] = grafo[i][j];

    // O coração do algoritmo
    for (int k = 0; k < V; k++) {          // Tenta usar k como intermediário
        for (int i = 0; i < V; i++) {      // De i
            for (int j = 0; j < V; j++) {  // Para j
                
                // Se passar por k é melhor que o caminho direto
                if (dist[i][k] != INF && dist[k][j] != INF && 
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

Características

  • Complexidade: \(O(V^3)\).
  • Limitação: Só viável para \(V \le 400 \sim 500\) (Maratonas: \(10^8\) operações = 1s).
  • Vantagem: Facílimo de implementar (5 linhas de lógica).
  • Ciclos Negativos: Se ao final dist[i][i] < 0, existe ciclo negativo envolvendo i.

4. Comparativo Geral

Algoritmo Tipo Pesos Negativos? Complexidade Uso Ideal
BFS 1 \(\to\) Todos Não (Só peso 1) \(O(V+E)\) Grafos sem peso.
Dijkstra 1 \(\to\) Todos Não \(O(E \log V)\) Grafos ponderados padrão.
Bellman-Ford 1 \(\to\) Todos Sim \(O(V \cdot E)\) Detecção de arbitragem/ciclos.
Floyd-Warshall Todos \(\to\) Todos Sim \(O(V^3)\) Grafos pequenos e densos.
Back to top