Algoritmo de Edmonds-Karp
O Algoritmo de Edmonds-Karp é uma forma eficiente de resolver o problema do fluxo máximo em redes de fluxo, sendo uma implementação específica do Algoritmo de Ford-Fulkerson. Sua principal característica é a escolha do caminho de aumento de fluxo mais curto em cada etapa, o que garante a conclusão do cálculo. Geralmente, esse caminho mais curto é encontrado usando uma busca em largura (BFS), que opera em tempo O(VE²). Embora seja assintoticamente mais lento que outros métodos como o algoritmo de remarcagem-para-frente (que roda em O(V²E)), o Edmonds-Karp costuma ser mais rápido em grafos esparsos. O algoritmo foi publicado inicialmente pelo cientista russo Dinic em 1970 e, de forma independente, por Edmonds e Karp em 1972. O algoritmo de Dinic aprimora essas técnicas, alcançando uma complexidade de tempo de O(V²E).
Pontos-chave
- Edmonds-Karp é uma implementação do Algoritmo de Ford-Fulkerson para fluxo máximo.
- Utiliza o caminho de aumento de fluxo mais curto em cada iteração.
- A busca em largura (BFS) encontra o caminho mais curto em tempo O(VE²).
- É eficiente para grafos esparsos, apesar de ser mais lento que outros métodos.
- Publicado por Dinic (1970) e Edmonds & Karp (1972).
Este algoritmo é essencialmente o mesmo que o de Ford-Fulkerson, mas com uma regra específica para a busca do caminho de aumento de fluxo. A diferença crucial é que ele sempre seleciona o caminho mais curto que ainda possui capacidade disponível. Essa escolha garante que o processo de encontrar o fluxo máximo termine.
Considere uma rede com sete nós e capacidades definidas. Nos arcos, a notação 'f/c' indica o fluxo atual ('f') e a capacidade total ('c'). A capacidade residual de um arco (u, v) é calculada como c_f(u, v) = c(u, v) - f(u, v), ou seja, a capacidade total menos o fluxo já utilizado. Se o fluxo em um arco for negativo, ele contribui positivamente para a capacidade residual. Por exemplo, o caminho A -> D -> E -> G tem uma capacidade residual mínima de min(3-0, 2-0, 1-0) = 1. Outro caminho, A -> D -> F -> G, tem capacidade residual mínima de min(3-1, 6-0, 9-0) = 2.
