Algoritmo de Ford-Fulkerson
De Wikipedia, a enciclopédia encyclopedia
O algoritmo de Ford-Fulkerson (assim designado em honra de Lester Randolph Ford, Jr e Delbert Ray Fulkerson) é um algoritmo utilizado para resolver problemas de fluxo em rede (network flow). O algoritmo é empregado quando se deseja encontrar um fluxo de valor máximo que faça o melhor uso possível das capacidades disponíveis na rede em questão.
A história do algoritmo está relacionada à análise da rede ferroviária da União Soviética, tanto por russos quanto por americanos, nas décadas de 1930, 1940 e 1950.[1]
O problema resolvido pelo algoritmo é o de encontrar um fluxo máximo em uma rede. Uma rede pode ser uma rede elétrica, um sistema de transporte de fluidos ou a distribuição de produtos ao longo de uma rede de transportes, como uma malha ferroviária ou rodoviária.[2] Por exemplo, deseja-se transportar o máximo de minério de ferro através de uma rede ferroviária, limitadas pela capacidade de cada via. O tratamento aqui dado ao algoritmo supõe a existência de um único “ponto de entrada” (uma fonte) e de um único “ponto de saída” (um terminal).
Para valores de fluxo irracionais, o algoritmo poderá ficar em um loop infinito e nunca retornar o fluxo máximo desejado. 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.