Algoritmo de Edmonds-Karp
O Algoritmo de Edmonds-Karp é uma implementação específica e eficiente do famoso Algoritmo de Ford-Fulkerson, utilizado para resolver o problema de fluxo máximo em redes. Sua principal característica é a garantia de término do cálculo, obtida ao sempre selecionar o caminho de aumento mais curto em cada iteração. Geralmente, esse caminho é encontrado por meio de uma busca em largura (BFS), resultando em uma complexidade assintótica de O(VE²). Embora seja assintoticamente mais lento que o algoritmo de 'remarcagem-para-frente' (que roda em O(V³)), o Edmonds-Karp frequentemente se mostra mais rápido em grafos esparsos. Publicado inicialmente pelo cientista russo Dinic em 1970, foi redescoberto e publicado independentemente por Edmonds e Karp em 1972. O algoritmo de Dinic, inclusive, incorpora técnicas adicionais que reduzem o tempo de execução para O(V²E).
Pontos-chave
- É uma implementação do Algoritmo de Ford-Fulkerson para fluxo máximo.
- Garante o término do cálculo ao usar o caminho de aumento mais curto em cada iteração.
- Geralmente utiliza Busca em Largura (BFS) para encontrar o caminho mais curto.
- Possui complexidade assintótica de O(VE²), sendo mais rápido em grafos esparsos que outras abordagens.
- Foi publicado por Dinic em 1970 e, independentemente, por Edmonds e Karp em 1972.
O Algoritmo de Edmonds-Karp é conceitualmente idêntico ao Algoritmo de Ford-Fulkerson, com uma distinção crucial: a forma como o caminho de aumento de fluxo é determinado. Em Edmonds-Karp, o algoritmo sempre busca e utiliza o caminho mais curto que ainda possui capacidade disponível para transportar fluxo.
Considere uma rede de fluxo com sete nós e capacidades definidas para cada arco. Em cada arco, a notação 'f/c' representa 'fluxo atual' (f) e 'capacidade total' (c). A capacidade residual de um nó 'u' para um nó 'v' é calculada como a capacidade total menos o fluxo que já está sendo utilizado (c_f(u,v) = c(u,v) - f(u,v)). Se o fluxo de 'u' para 'v' for negativo, isso contribui para a capacidade residual. O algoritmo busca o caminho de menor capacidade residual para aumentar o fluxo. Por exemplo, em um caminho A-D-E-G, se as capacidades residuais forem (3-0), (2-0), (1-0), o mínimo é 1, então o fluxo pode ser aumentado em 1 unidade. Em outro caminho A-D-F-G, com capacidades residuais (3-1), (6-0), (9-0), o mínimo é 2, permitindo um aumento de 2 unidades de fluxo.
