Algoritmo de Ford-Fulkerson
Origem: Wikipédia, a enciclopédia livre.
O algoritmo de Ford-Fulkerson (assim designado em honra de L. R. Ford e D. R. Fulkerson) calcula o fluxo máximo numa rede de fluxos.
Funciona pela definição de um caminho de aumento de fluxo num grafo. Ao acrescentarmos o caminho de aumento ao fluxo já existente no grafo, o fluxo máximo é atingido quando não for possível descobrir mais caminhos de aumento. Contudo, não há qualquer certeza que se chegue a esta situação – o mais que se pode garantir é que a resposta estará correcta se o algoritmo terminar. No caso de este algoritmo manter-se com iterações sucessivas ad infinitum, o fluxo poderá nunca convergir para um fluxo máximo. Todavia, esta situação ocorre apenas para valores de fluxo irracionais.
O algoritmo de Edmonds-Karp é uma variação do algoritmo de Ford-Fulkerson, mas com um final garantido e com um tempo de execução independente do valor do fluxo máximo.
[editar] Pseudocódigo
function Ford-Fulkerson(G, s, t)
for each (u, v) in E[G]
fluxo(u, v) := 0
fluxo(v, u) := 0
while existe caminho de aumento p de s para t na rede residual
Cf(p) := capacidade do arco de menor capacidade em p
for each (u, v) em p
fluxo(u, v) := fluxo(u, v) + Cf(p)
fluxo(v, u) := -fluxo(u, v)
