Fluxo Máximo: Ford-Fulkerson e Edmonds-Karp

1. O Problema do Encanamento

Temos uma rede de tubulações conectando uma represa (Fonte \(S\)) a uma cidade (Sorvedouro \(T\)). Cada cano tem um diâmetro (Capacidade) diferente. Qual é a quantidade máxima de água que consegue chagar na cidade por segundo?

Teorema do Corte Mínimo (Max-Flow Min-Cut): O fluxo máximo possível de \(S\) a \(T\) é exatamente igual à capacidade do “gargalo” (corte mínimo) que separa \(S\) de \(T\). Ou seja, a vazão da rede é limitada pelo conjunto de canos mais restritivo.

2. Conceito de Grafo Residual

A grande sacada do algoritmo Ford-Fulkerson é a capacidade de desfazer decisões. - Se enviamos 5 litros de \(A \to B\), criamos uma “aresta reversa” virtual \(B \to A\) com capacidade 5. - Isso significa que podemos “devolver” até 5 litros de \(B\) para \(A\) se acharmos um caminho melhor depois. - O Grafo Residual contém as capacidades restantes + capacidades reversas.

3. Algoritmo de Edmonds-Karp

É a implementação do método Ford-Fulkerson usando BFS para encontrar o caminho mais curto (em número de arestas) no grafo residual a cada iteração.

  1. Enquanto existir um caminho de \(S\) para \(T\) no Grafo Residual (achado por BFS):
    • Encontre o Gargalo (\(bottleneck\)) desse caminho (a menor capacidade encontrada).
    • Some esse gargalo ao fluxo total.
    • Atualize o grafo residual:
      • Subtraia o gargalo das arestas de ida (cap[u][v] -= gargalo).
      • Some o gargalo nas arestas de volta (cap[v][u] += gargalo).

4. Implementação Java

Para Fluxo, a Matriz de Adjacência (adj[u][v] = capacidade) é muito mais fácil de implementar que lista de adjacência, desde que \(V \le 500\).

import java.util.*;

public class MaxFlow {
    static final int INF = Integer.MAX_VALUE;
    
    // Retorna o fluxo máximo de s para t
    public static int edmondsKarp(int N, int[][] capacity, int s, int t) {
        int flow = 0;
        int[] parent = new int[N]; // Para reconstruir o caminho
        
        while (true) {
            // 1. BFS para encontrar caminho aumentante no grafo residual
            Arrays.fill(parent, -1);
            Queue<Integer> q = new LinkedList<>();
            q.add(s);
            parent[s] = s;
            
            while (!q.isEmpty()) {
                int u = q.poll();
                if (u == t) break; // Chegou no destino
                
                for (int v = 0; v < N; v++) {
                    // Se não visitado E tem capacidade residual > 0
                    if (parent[v] == -1 && capacity[u][v] > 0) {
                        parent[v] = u;
                        q.add(v);
                    }
                }
            }
            
            // Se não chegou em t, acabaram os caminhos. Fim.
            if (parent[t] == -1) break;
            
            // 2. Achar o gargalo (bottleneck) do caminho encontrado
            int push = INF;
            int curr = t;
            while (curr != s) {
                int prev = parent[curr];
                push = Math.min(push, capacity[prev][curr]);
                curr = prev;
            }
            
            // 3. Atualizar capacidades residuais (Ida e Volta)
            flow += push;
            curr = t;
            while (curr != s) {
                int prev = parent[curr];
                capacity[prev][curr] -= push; // Diminui ida
                capacity[curr][prev] += push; // Aumenta volta (residual)
                curr = prev;
            }
        }
        
        return flow;
    }

    public static void main(String[] args) {
        int N = 4;
        int[][] capacity = new int[N][N];
        
        // Exemplo: S=0, T=3
        capacity[0][1] = 1000;
        capacity[0][2] = 1000;
        capacity[1][2] = 1;    // Aresta crítica
        capacity[1][3] = 1000;
        capacity[2][3] = 1000;
        
        System.out.println("Fluxo Maximo: " + edmondsKarp(N, capacity, 0, 3));
    }
}

Complexidade

  • Edmonds-Karp: \(O(V \cdot E^2)\).
  • Dinic (Melhorado): \(O(V^2 \cdot E)\). Implementado com “Level Graph” (BFS) e “Blocking Flow” (DFS). Preferido em maratonas para \(V > 500\) ou muitos casos de teste.

5. Aplicações Surpreendentes

Fluxo máximo resolve muito mais que “água em canos”: 1. Emparelhamento Máximo Bipartido: É um caso especial de fluxo (vide módulo anterior). 2. Corte Mínimo em Imagens: Usado para segmentação de objetos (Photoshop Select Subject). 3. Alocação de Tarefas: Com prioridades e capacidades. 4. Circulação com Demandas: Equilibrar oferta e demanda em logística.

Back to top