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 $G=(N,A)$, sendo $N$ o conjunto de nós e $A$ o conjunto de arestas, dotado das seguintes propriedades:

• Para cada aresta $a\in A$ há um número não negativo $c_{a}$, 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 $s$;
• Existe um único nó que será identificado como terminal (ou sumidouro) $t$, tal que $t\in N$;
• Não há nenhuma aresta direcionada para a fonte $s$, apenas arestas que saem dela e são direcionadas para outros nós.
• Não há nenhuma aresta que saia do terminal $t$, apenas arestas direcionadas a ele.

Um fluxo é uma função $f:A\rightarrow \mathbb {R_{+}} \,$ que respeite as seguintes propriedades:

• Restrições de capacidade (capacity conditions): Para cada $a\in A$, temos que $0\leq f(a)\leq c_{a}$.
• Restrições de conservação (conservation conditions): Para cada nó $n\in N$ diferente de $s$ e $t$, 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 $v(f)=\sum _{a\in out(s)}f(a)$ (sendo $out(s)$ o conjunto de arestas que sai de $s$), o problema a ser resolvido é, dada uma rede de fluxo $G$, achar um fluxo $f$ tal que $v(f)$ seja o máximo possível.

O Algoritmo

Animação representando o Algoritmo de Ford-Fulkerson para problemas de maximização de fluxo em rede. À esquerda o grafo original e à direita seu grafo residual. A cor azul representa o caminho simples s-t escolhido;a cor vermelha representa o novo fluxo no grafo original;a linha pontilhada representa as novas arestas do grafo residual.

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 ($G_{R}$) , que é construído da seguinte forma:

• O conjunto de nós de $G_{R}$ é o mesmo de $G$;
• Ao percorrer as arestas em $G$, vamos criando as arestas de $G_{R}$ do seguinte modo:
  • Para cada aresta $a=(n_{i},n_{j})$ de $G$ - sai do nó $n_{i}$ e entra no nó $n_{j})$ - que possui fluxo $f(a)<c_{a}$, adicionamos uma aresta $a_{R}=(n_{i},n_{j})$ com capacidade $c_{a}{_{R}}=c_{a}-f(a)$ e $f(a_{R})=0$. Deste modo, estamos definindo a possibilidade de “empurrar para frente” a quantidade de fluxo que a aresta $a$ conseguiria carregar a mais.
  • Para cada aresta $a=(n_{i},n_{j})$ de $G$ tal que $f(a)>0$, 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 $a'_{R}=(n_{i},n_{j})$ em $G_{R}$ com direção inversa a $a$ e capacidade $c_{a'_{R}}=f(a)$ Assim como no passo anterior, o fluxo de $a'_{R}$ no grafo residual é nulo.

Observação: Cada aresta do grafo original $G$ pode dar origem a no máximo duas arestas correspondentes a ela no grafo residual, já que se $a$ 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, $G_{R}$ pode possuir até duas vezes o número de arestas de $G$.

Assim, para definir como será feito o aumento gradual de fluxo que entrará na rede (ou seja, em $G$), 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 $G_{R}$ aquele que vai da fonte $s$ até o terminal $t$ 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 $c_{a_{R}}$ (capacidade). Vamos chamar tal valor de $b$;
• Analisamos cada aresta $a_{R}=(n_{i},n_{j})$ do caminho escolhido. Se $a_{R}$ possui direção s-t (i.e., a mesma direção que possui no gráfo original, levando o fluxo de $s$ para $t$), então procuramos a aresta correspondente $a=(n_{i},n_{j})$ em $G$ e aumentamos seu fluxo $f(a)$ em $b$ unidades: $f(a)_{depois}=f(a)_{antes}+b$.

Em contrapartida, se $a_{R}=(n_{i},n_{j})$ possuir direção inversa (apontando de $t$ para $s$), então modificamos a sua correspondente em G diminuindo seu fluxo em $b$ unidades: $f(a)_{depois}=f(a)_{antes}-b$ ;

• Reconfiguramos $G_{R}$ para os novos valores das arestas de $G$ 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 $f$ presente em $G$ 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 $c_{a}$, a complexidade do algoritmo é $O(mf)$, em que $m$ representa o número de arestas presentes no grafo $G$ e $f$ 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 $s$-$t$ no grafo residual em $O(m+n)$, tal que $n$ é o número total de nós do grafo. Supondo que todos os nós possuem pelo menos uma aresta incidente, podemos afirmar que $m>n/2$ e, portanto, simplificamos a expressão anterior para $O(m)$. 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 $O(mf)$ para atingir o fluxo máximo desejado.