Algoritmo de Ford-Fulkerson

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.

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. 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.

Definições  

Uma rede de fluxo é um grafo direcionado , sendo  o conjunto de nós e  o conjunto de arestas, dotado das seguintes propriedades:
Para cada aresta  há um número não negativo , que indica a capacidade da mesma (ou seja, a quantidade máxima de fluxo que cada uma é capaz de carregar).
Existe um único nó que será identificado como fonte (source), a ser denotado por ;
Existe um único nó que será identificado como terminal (ou sumidouro) , tal que ;
Não há nenhuma aresta direcionada para a fonte , apenas arestas que saem dela e são direcionadas para outros nós.
Não há nenhuma aresta que saia do terminal , apenas arestas direcionadas a ele.

Um fluxo é uma função   que respeite as seguintes propriedades:
Restrições de capacidade (capacity conditions): Para cada , temos que .
Restrições de conservação (conservation conditions): Para cada nó  diferente de  e , temos que o fluxo total que entra em determinado nó é igual ao fluxo total que sai de tal nó.

Para evitar comportamentos patológicos, em geral se supõe que os valores das capacidades são inteiros (o que acarreta, neste algoritmo, em valores de fluxos inteiros).

Definindo o valor de um fluxo como  (sendo  o conjunto de arestas que sai de ), o problema a ser resolvido é, dada uma rede de fluxo , achar um fluxo   tal que  seja o máximo possível.

O Algoritmo

Começamos supondo que o fluxo inicial em todas as arestas é nulo. Desta forma, iremos aumentar gradativamente este valor acrescentando fluxo na fonte através de algumas regras básicas.

A ideia principal do algoritmo gira em torno de duas operações: quando uma aresta possui menos fluxo do que permite a sua capacidade (o que inclui possuir fluxo nulo), temos a opção de “empurrar” fluxo na sua direção (“empurrar fluxo à frente”); do mesmo modo, quando uma aresta possui uma quantidade positiva de fluxo, seja ela menor ou igual à sua capacidade, temos a opção de fazer com que esse fluxo retroceda, “empurrando-o para trás”, ou seja, na direção contrária.

Para concretizar tais operações, definimos primeiramente um grafo auxiliar que vamos chamar de grafo residual () , que é construído da seguinte forma:

O conjunto de nós de  é o mesmo de ;
Ao percorrer as arestas em , vamos criando as arestas de  do seguinte modo:
Para cada aresta  de  - sai do nó  e entra no nó  - que possui fluxo , adicionamos uma aresta  com capacidade  e . Deste modo, estamos definindo a possibilidade de “empurrar para frente” a quantidade de fluxo que a aresta  conseguiria carregar a mais.
Para cada aresta  de  tal que , ou seja, cada aresta que já esteja carregando alguma quantidade positiva de fluxo, existe a possibilidade de empurrar este fluxo para trás, se assim desejarmos. Desta forma, adicionamos uma aresta  em  com direção inversa a  e capacidade  Assim como no passo anterior, o fluxo de  no grafo residual é nulo.

Observação: Cada aresta do grafo original  pode dar origem a no máximo duas arestas correspondentes a ela no grafo residual, já que se  possuir um fluxo positivo que seja menor que sua capacidade, uma aresta de mesma direção será criada para representar o fluxo a mais que ainda pode ser carregado, e uma aresta de direção oposta será inserida para representar o fluxo existente que pode retroceder caso seja necessário para a otimização do problema. Resumindo,  pode possuir até duas vezes o número de arestas de .

Assim, para definir como será feito o aumento gradual de fluxo que entrará na rede (ou seja, em ), até que o máximo seja atingido, o restante do algoritmo baseia-se principalmente no grafo residual, alterando sua configuração a cada aumento realizado.Os passos seguintes realizados pelo algoritmo, após a criação do grafo residual, estão descritos a seguir:

Seja um caminho simples s-t de  aquele que vai da fonte  até o terminal  passando por cada aresta uma única vez. O primeiro passo do algoritmo é encontrar um caminho simples s-t qualquer que exista no grafo residual. Esse caminho é chamado de caminho de aumento;
Escolhido o caminho de aumento, o segundo passo é procurar a aresta pertencente a ele que possui o menor valor  (capacidade). Vamos chamar tal valor de ;
Analisamos cada aresta  do caminho escolhido. Se  possui direção s-t (i.e., a mesma direção que possui no gráfo original, levando o fluxo de  para ), então procuramos a aresta correspondente  em  e aumentamos seu fluxo  em  unidades: .
Em contrapartida, se  possuir direção inversa (apontando de  para ), então modificamos a sua correspondente em G diminuindo seu fluxo em  unidades:  ;
Reconfiguramos  para os novos valores das arestas de  e repetimos os passos anteriores até que nao haja mais nenhum caminho de aumento no grafo residual para ser analisado. Quando isso acontecer, o fluxo  presente em  será o fluxo máximo.

Pseudocódigo

 função Atualiza-Grafo-Residual(G, f)
     Para cada aresta a(u,v) em G, , com u,v∈N
            Se f(a) < ca então
                insira aR(u,v) com caR=(ca - f(a))
            Se f(a) > 0 então
                insira aR(v,u) com caR=f(a)
      Retorna(GR)

 função Ford-Fulkerson(G, s, t)
    Inicia f(a)=0 para cada aresta a de G
    Defina GR = Atualiza-Grafo-Residual(G, f)
    Enquanto existir caminho de aumento de s para t em GR
         Seja P um caminho de aumento s-t em GR
         Defina cP = min{caR : aR∈P}
         Para cada aresta aR em P
             Se aR tem direção s-t então
                  faça [f(a) → f(a) + cP] em G
            Caso contrário
                 faça [f(a) → f(a) - cP] em G
         GR = Atualiza-Grafo-Residual(G, f)
   Retorna (f)

Complexidade 
Para valores inteiros de , a complexidade do algoritmo é , em que  representa o número de arestas presentes no grafo  e  o fluxo máximo encontrado. Utilizando uma busca em largura (breadth-first search) ou uma busca em profundidade  (depth-first search), é possível encontrar um caminho simples - no grafo residual em , tal que  é o número total de nós do grafo. Supondo que todos os nós possuem pelo menos uma aresta incidente, podemos afirmar que  e, portanto, simplificamos a expressão 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ção serão sempre maiores ou iguais a 1, por as capacidades serem inteiras, podemos concluir que o algoritmo irá rodar em no máximo  para atingir o fluxo máximo desejado.

Algoritmos de grafos
Algoritmos de otimização
Pesquisa operacional