b'\n_START_ARTICLE_\nAlgoritmo de Ford-Fulkerson\n_START_PARAGRAPH_\nO algoritmo de Ford-Fulkerson (assim designado em honra de Lester Randolph Ford, Jr e Delbert Ray Fulkerson) \xc3\xa9 um algoritmo utilizado para resolver problemas de fluxo em rede (network flow). O algoritmo \xc3\xa9 empregado quando se deseja encontrar um fluxo de valor m\xc3\xa1ximo que fa\xc3\xa7a o melhor uso poss\xc3\xadvel das capacidades dispon\xc3\xadveis na rede em quest\xc3\xa3o._NEWLINE_A hist\xc3\xb3ria do algoritmo est\xc3\xa1 relacionada \xc3\xa0 an\xc3\xa1lise da rede ferrovi\xc3\xa1ria da Uni\xc3\xa3o Sovi\xc3\xa9tica, tanto por russos quanto por americanos, nas d\xc3\xa9cadas de 1930, 1940 e 1950._NEWLINE_O problema resolvido pelo algoritmo \xc3\xa9 o de encontrar um fluxo m\xc3\xa1ximo em uma rede. Uma rede pode ser uma  rede el\xc3\xa9trica, um sistema de  transporte de fluidos ou a distribui\xc3\xa7\xc3\xa3o de produtos ao longo de uma rede de transportes, como uma malha ferrovi\xc3\xa1ria ou  rodovi\xc3\xa1ria. Por exemplo, deseja-se transportar o m\xc3\xa1ximo de min\xc3\xa9rio de ferro atrav\xc3\xa9s de uma rede ferrovi\xc3\xa1ria, limitadas pela capacidade de cada via. O tratamento aqui dado ao algoritmo sup\xc3\xb5e a exist\xc3\xaancia de um \xc3\xbanico \xe2\x80\x9cponto de entrada\xe2\x80\x9d (uma fonte) e de um \xc3\xbanico \xe2\x80\x9cponto de sa\xc3\xadda\xe2\x80\x9d (um terminal)._NEWLINE_Para valores de fluxo irracionais, o algoritmo poder\xc3\xa1 ficar em um loop infinito e nunca retornar o fluxo m\xc3\xa1ximo desejado. O algoritmo de Edmonds-Karp \xc3\xa9 uma varia\xc3\xa7\xc3\xa3o do algoritmo de Ford-Fulkerson, mas com um final garantido e com um tempo de execu\xc3\xa7\xc3\xa3o independente do valor do fluxo m\xc3\xa1ximo.\n_START_SECTION_\nPseudoc\xc3\xb3digo\n_START_PARAGRAPH_\nfun\xc3\xa7\xc3\xa3o Atualiza-Grafo-Residual(G, f)_NEWLINE_    Para cada aresta a(u,v) em G, , com u,v\xe2\x88\x88N_NEWLINE_           Se f(a) < c\xe2\x82\x90 ent\xc3\xa3o_NEWLINE_               insira aR(u,v) com c\xe2\x82\x90R=(c\xe2\x82\x90 - f(a))_NEWLINE_           Se f(a) > 0 ent\xc3\xa3o_NEWLINE_               insira aR(v,u) com c\xe2\x82\x90R=f(a)_NEWLINE_     Retorna(GR)_NEWLINE_fun\xc3\xa7\xc3\xa3o Ford-Fulkerson(G, s, t)_NEWLINE_   Inicia f(a)=0 para cada aresta a de G_NEWLINE_   Defina GR = Atualiza-Grafo-Residual(G, f)_NEWLINE_   Enquanto existir caminho de aumento de s para t em GR_NEWLINE_        Seja P um caminho de aumento s-t em GR_NEWLINE_        Defina cP = min{caR\xc2\xa0: aR\xe2\x88\x88P}_NEWLINE_        Para cada aresta aR em P_NEWLINE_            Se aR tem dire\xc3\xa7\xc3\xa3o s-t ent\xc3\xa3o_NEWLINE_                 fa\xc3\xa7a [f(a) \xe2\x86\x92 f(a) + cP] em G_NEWLINE_           Caso contr\xc3\xa1rio_NEWLINE_                fa\xc3\xa7a [f(a) \xe2\x86\x92 f(a) - cP] em G_NEWLINE_        GR = Atualiza-Grafo-Residual(G, f)_NEWLINE_  Retorna (f)\n_START_SECTION_\nComplexidade\n_START_PARAGRAPH_\nPara valores inteiros de , a complexidade do algoritmo \xc3\xa9 , em que  representa o n\xc3\xbamero de arestas presentes no grafo  e  o fluxo m\xc3\xa1ximo encontrado. Utilizando uma busca em largura (breadth-first search) ou uma busca em profundidade  (depth-first search), \xc3\xa9 poss\xc3\xadvel encontrar um caminho simples - no grafo residual em , tal que  \xc3\xa9 o n\xc3\xbamero total de n\xc3\xb3s do grafo. Supondo que todos os n\xc3\xb3s possuem pelo menos uma aresta incidente, podemos afirmar que  e, portanto, simplificamos a express\xc3\xa3o anterior para . Cada caminho simples encontrado resulta em um novo fluxo a ser acrescentado no grafo original. Como os incrementos de fluxo obtidos em cada itera\xc3\xa7\xc3\xa3o ser\xc3\xa3o sempre maiores ou iguais a 1, por as capacidades serem inteiras, podemos concluir que o algoritmo ir\xc3\xa1 rodar em no m\xc3\xa1ximo  para atingir o fluxo m\xc3\xa1ximo desejado.'