Algoritmo de Edmonds-Karp
O Algoritmo de Edmonds-Karp é uma abordagem eficiente para resolver o problema de fluxo máximo em redes. Ele se baseia no método geral de Ford-Fulkerson, mas se destaca por sempre escolher o caminho de menor comprimento para aumentar o fluxo em cada etapa. Essa estratégia garante que o algoritmo sempre termine. Geralmente, a busca pelo caminho mais curto é feita usando uma busca em largura (BFS), que tem uma complexidade de tempo de O(VE²). Embora seja mais lento que outros métodos como o algoritmo de Dinic (O(V²E)), o Edmonds-Karp pode ser mais rápido em grafos esparsos. O algoritmo foi publicado inicialmente por Dinic em 1970 e, de forma independente, por Edmonds e Karp em 1972.
Pontos-chave
- Edmonds-Karp resolve o problema de fluxo máximo em redes.
- Utiliza o caminho de aumento mais curto em cada iteração.
- A busca em largura (BFS) encontra o caminho mais curto.
- Tem complexidade de tempo O(VE²), ideal para grafos esparsos.
- Publicado por Dinic (1970) e Edmonds & Karp (1972).
Este algoritmo é uma variação do Algoritmo de Ford-Fulkerson. A principal diferença reside na forma como o caminho de aumento de fluxo é selecionado: o Edmonds-Karp sempre busca o caminho mais curto que ainda possui capacidade disponível.
Considere uma rede com sete nós e capacidades definidas. A notação 'f/c' em cada arco representa o fluxo atual (f) e a capacidade total (c). A capacidade residual de um arco (u, v) é calculada como a capacidade total menos o fluxo já utilizado: c_f(u, v) = c(u, v) - f(u, v). Se o fluxo em um arco for negativo, ele contribui para a capacidade residual. Por exemplo, no caminho A->D->E->G, o fluxo mínimo é min(3-0, 2-0, 1-0) = 1. Em outro caminho, A->D->F->G, o fluxo mínimo é min(3-1, 6-0, 9-0) = 2.
