Algoritmo de Ford-Fulkerson

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde agosto de 2010).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

O algoritmo de Ford-Fulkerson (assim designado em honra de Lester Randolph Ford junior e Delbert Ray 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.

Pseudocódigo[editar | editar código-fonte]

 função Ford-Fulkerson(G, s, t)
   para cada (u, v) em E[G]
     fluxo(u, v) := 0
     fluxo(v, u) := 0
   enquanto existir caminho de aumento p de s para t na rede residual
     Cf(p) := capacidade do arco de menor capacidade em p
     para cada (u, v) em p
       fluxo(u, v) := fluxo(u, v) + Cf(p)
       fluxo(v, u) := -fluxo(u, v)
     faça a rede residual Gf(Vf,Ef), em que Cf(u,v) := c(u,v) - fluxo(u,v)

Em cada iteração buscamos um caminho por onde podemos passar fluxo. Passamos o fluxo por aí e montamos uma rede residual (que, de forma também simplificada, é uma rede equivalente à original com aquele caminho revertido). O que muda nos diversos algoritmos que se baseiam no Método de Ford-Fulkerson é o modo de achar o "augmenting path". A idéia é fazer uma busca no subgrafo de G formado pelas arestas onde f(u,v) < c(u,v). O algoritmo usando DFS tem complexidade O(E.maxflow), o algoritmo usando BFS (conhecido como Algoritmo de Edmonds-Karp) tem complexidade O(V E^2). Outra alternativa é usar o PFS (Priority First Search), que busca os caminhos com maior capacidade.

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
O Commons possui uma categoria contendo imagens e outros ficheiros sobre Algoritmo de Ford-Fulkerson