Algoritmo Ford – Fulkerson - Ford–Fulkerson algorithm

O método de Ford-Fulkerson ou algoritmo de Ford-Fulkerson ( FFA ) é um algoritmo mais que calcula o fluxo máximo em uma rede de fluxo . Às vezes, é chamado de "método" em vez de "algoritmo", pois a abordagem para encontrar caminhos crescentes em um gráfico residual não é totalmente especificada ou é especificada em várias implementações com diferentes tempos de execução. Foi publicado em 1956 por LR Ford Jr. e DR Fulkerson . O nome "Ford-Fulkerson" também é freqüentemente usado para o algoritmo Edmonds-Karp , que é uma implementação totalmente definida do método Ford-Fulkerson.

A ideia por trás do algoritmo é a seguinte: enquanto houver um caminho da fonte (nó inicial) até o coletor (nó final), com capacidade disponível em todas as arestas do caminho, enviamos o fluxo ao longo de um dos caminhos. Então encontramos outro caminho e assim por diante. Um caminho com capacidade disponível é chamado de caminho crescente .

Algoritmo

Seja um gráfico e, para cada aresta de u a v , seja a capacidade e o fluxo. Queremos encontrar o fluxo máximo da fonte s para o coletor t . Após cada etapa do algoritmo, o seguinte é mantido: ${\ displaystyle G (V, E)}$${\ displaystyle c (u, v)}$${\ displaystyle f (u, v)}$

Restrições de capacidade	${\ displaystyle \ forall (u, v) \ in E: \ f (u, v) \ leq c (u, v)}$	O fluxo ao longo de uma borda não pode exceder sua capacidade.
Simetria de enviesamento	${\ displaystyle \ forall (u, v) \ in E: \ f (u, v) = - f (v, u)}$	O fluxo líquido de u para v deve ser o oposto do fluxo líquido de v para u (veja o exemplo).
Conservação de fluxo	${\ displaystyle \ forall u \ in V: u \ neq s {\ text {e}} u \ neq t \ Rightarrow \ sum _ {w \ in V} f (u, w) = 0}$	O fluxo líquido para um nó é zero, exceto para a fonte, que "produz" fluxo, e o sumidouro, que "consome" fluxo.
Valor (f)	${\ displaystyle \ sum _ {(s, u) \ in E} f (s, u) = \ sum _ {(v, t) \ in E} f (v, t)}$	O fluxo que sai de s deve ser igual ao fluxo que chega a t .

Isso significa que o fluxo pela rede é um fluxo legal após cada rodada do algoritmo. Definimos a rede residual como a rede com capacidade e sem fluxo. Observe que pode acontecer que um fluxo de v para u seja permitido na rede residual, embora não seja permitido na rede original: se e então . ${\ displaystyle G_ {f} (V, E_ {f})}$${\ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}$${\ displaystyle f (u, v)> 0}$${\ displaystyle c (v, u) = 0}$${\ displaystyle c_ {f} (v, u) = c (v, u) -f (v, u) = f (u, v)> 0}$

Algorithm Ford–Fulkerson

O caminho na etapa 2 pode ser encontrado com, por exemplo, uma pesquisa em largura (BFS) ou uma pesquisa em profundidade em . Se você usar o primeiro, o algoritmo é chamado de Edmonds – Karp . ${\ displaystyle G_ {f} (V, E_ {f})}$

Quando não for possível encontrar mais caminhos na etapa 2, s não será capaz de alcançar t na rede residual. Se S é o conjunto de nós alcançáveis ​​por s na rede residual, então a capacidade total na rede original de arestas de S para o restante de V é, por um lado, igual ao fluxo total que encontramos de s para t , e por outro lado, serve como um limite superior para todos esses fluxos. Isso prova que o fluxo que encontramos é máximo. Veja também o teorema do corte mínimo do fluxo máximo .

Se o gráfico tiver várias fontes e sumidouros, agiremos da seguinte maneira: Suponha que e . Adicione uma nova fonte com uma borda de para cada nó , com capacidade . E adicione um novo coletor com uma borda de cada nó para , com capacidade . Em seguida, aplique o algoritmo Ford – Fulkerson. ${\ displaystyle G (V, E)}$${\ displaystyle T = \ {t \ mid t {\ text {é uma pia}} \}}$${\ displaystyle S = \ {s \ mid s {\ text {é uma fonte}} \}}$${\ displaystyle s ^ {*}}$${\ displaystyle (s ^ {*}, s)}$${\ displaystyle s ^ {*}}$${\ displaystyle s \ in S}$${\ displaystyle c (s ^ {*}, s) = d_ {s} \; (d_ {s} = \ sum _ {(s, u) \ in E} c (s, u))}$${\ displaystyle t ^ {*}}$${\ displaystyle (t, t ^ {*})}$${\ displaystyle t \ in T}$${\ displaystyle t ^ {*}}$${\ displaystyle c (t, t ^ {*}) = d_ {t} \; (d_ {t} = \ sum _ {(v, t) \ in E} c (v, t))}$

Além disso, se um nó u tiver restrição de capacidade , substituímos esse nó por dois nós e uma aresta com capacidade . Em seguida, aplique o algoritmo Ford – Fulkerson. ${\ displaystyle d_ {u}}$${\ displaystyle u _ {\ mathrm {in}}, u _ {\ mathrm {out}}}$${\ displaystyle (u _ {\ mathrm {in}}, u _ {\ mathrm {out}})}$${\ displaystyle c (u _ {\ mathrm {in}}, u _ {\ mathrm {out}}) = d_ {u}}$

Complexidade

Ao adicionar o caminho de aumento de fluxo ao fluxo já estabelecido no gráfico, o fluxo máximo será alcançado quando nenhum caminho de aumento de fluxo puder ser encontrado no gráfico. No entanto, não há certeza de que essa situação será atingida, então o melhor que pode ser garantido é que a resposta estará correta se o algoritmo terminar. No caso de o algoritmo funcionar para sempre, o fluxo pode nem mesmo convergir para o fluxo máximo. No entanto, esta situação ocorre apenas com valores de fluxo irracionais. Quando as capacidades são inteiras, o tempo de execução de Ford – Fulkerson é limitado por (veja a notação grande O ), onde é o número de arestas no gráfico e é o fluxo máximo no gráfico. Isso ocorre porque cada caminho de aumento pode ser encontrado no tempo e aumenta o fluxo em uma quantidade inteira de pelo menos , com o limite superior . ${\ displaystyle O (Ef)}$${\ displaystyle E}$${\ displaystyle f}$${\ displaystyle O (E)}$${\ displaystyle 1}$${\ displaystyle f}$

Uma variação do algoritmo Ford-Fulkerson com término garantido e tempo de execução independente do valor de fluxo máximo é o algoritmo Edmonds-Karp , que funciona no tempo. ${\ displaystyle O (VE ^ {2})}$

Exemplo integral

O exemplo a seguir mostra as primeiras etapas de Ford – Fulkerson em uma rede de fluxo com 4 nós, fonte e coletor . Este exemplo mostra o pior caso de comportamento do algoritmo. Em cada etapa, apenas um fluxo de é enviado pela rede. Se, em vez disso, fosse usada a pesquisa ampla, apenas duas etapas seriam necessárias. ${\ displaystyle A}$${\ displaystyle D}$${\ displaystyle 1}$

Caminho	Capacidade	Rede de fluxo resultante
Rede de fluxo inicial
${\ displaystyle A, B, C, D}$	${\ displaystyle {\ begin {alinhado} & \ min (c_ {f} (A, B), c_ {f} (B, C), c_ {f} (C, D)) \\ = {} & \ min (c (A, B) -f (A, B), c (B, C) -f (B, C), c (C, D) -f (C, D)) \\ = {} & \ min (1000-0,1-0,1000-0) = 1 \ end {alinhado}}}$
${\ displaystyle A, C, B, D}$	${\ displaystyle {\ begin {alinhado} & \ min (c_ {f} (A, C), c_ {f} (C, B), c_ {f} (B, D)) \\ = {} & \ min (c (A, C) -f (A, C), c (C, B) -f (C, B), c (B, D) -f (B, D)) \\ = {} & \ min (1000-0,0 - (- 1), 1000-0) = 1 \ end {alinhado}}}$
Depois de 1998 mais etapas ...
Rede de fluxo final

Observe como o fluxo é "empurrado" de para ao encontrar o caminho . ${\ displaystyle C}$${\ displaystyle B}$${\ displaystyle A, C, B, D}$

Exemplo de não terminação

Considere a rede de fluxo mostrado à direita, com a fonte , pia , capacidades das bordas , e , respectivamente , e e a capacidade de todas as outras bordas algum inteiro . A constante foi escolhida assim, isso . Usamos caminhos aumentantes de acordo com a tabela a seguir, onde , e . ${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle e_ {1}}$${\ displaystyle e_ {2}}$${\ displaystyle e_ {3}}$${\ displaystyle 1}$${\ displaystyle r = ({\ sqrt {5}} - 1) / 2}$${\ displaystyle 1}$${\ displaystyle M \ geq 2}$${\ displaystyle r}$${\ displaystyle r ^ {2} = 1-r}$${\ displaystyle p_ {1} = \ {s, v_ {4}, v_ {3}, v_ {2}, v_ {1}, t \}}$${\ displaystyle p_ {2} = \ {s, v_ {2}, v_ {3}, v_ {4}, t \}}$${\ displaystyle p_ {3} = \ {s, v_ {1}, v_ {2}, v_ {3}, t \}}$

Etapa	Caminho de aumento	Fluxo enviado	Capacidades residuais
			${\ displaystyle e_ {1}}$	${\ displaystyle e_ {2}}$	${\ displaystyle e_ {3}}$
0			${\ displaystyle r ^ {0} = 1}$	${\ displaystyle r}$	${\ displaystyle 1}$
1	${\ displaystyle \ {s, v_ {2}, v_ {3}, t \}}$	${\ displaystyle 1}$	${\ displaystyle r ^ {0}}$	${\ displaystyle r ^ {1}}$	${\ displaystyle 0}$
2	${\ displaystyle p_ {1}}$	${\ displaystyle r ^ {1}}$	${\ displaystyle r ^ {2}}$	${\ displaystyle 0}$	${\ displaystyle r ^ {1}}$
3	${\ displaystyle p_ {2}}$	${\ displaystyle r ^ {1}}$	${\ displaystyle r ^ {2}}$	${\ displaystyle r ^ {1}}$	${\ displaystyle 0}$
4	${\ displaystyle p_ {1}}$	${\ displaystyle r ^ {2}}$	${\ displaystyle 0}$	${\ displaystyle r ^ {3}}$	${\ displaystyle r ^ {2}}$
5	${\ displaystyle p_ {3}}$	${\ displaystyle r ^ {2}}$	${\ displaystyle r ^ {2}}$	${\ displaystyle r ^ {3}}$	${\ displaystyle 0}$

Note-se que após o passo 1, bem como depois do passo 5, as capacidades residuais de arestas , e estão sob a forma , e , respectivamente, para alguns . Isto significa que podemos usar caminhos aumentantes , , e um número infinito de vezes e capacidades residuais desses bordas estarão sempre na mesma forma. O fluxo total na rede após a etapa 5 é . Se continuarmos a usar caminhos de aumento como acima, o fluxo total converge para . No entanto, observe que há um fluxo de valor , enviando unidades de fluxo , 1 unidade de fluxo e unidades de fluxo . Portanto, o algoritmo nunca termina e o fluxo nem mesmo converge para o fluxo máximo. ${\ displaystyle e_ {1}}$${\ displaystyle e_ {2}}$${\ displaystyle e_ {3}}$${\ displaystyle r ^ {n}}$${\ displaystyle r ^ {n + 1}}$${\ displaystyle 0}$${\ displaystyle n \ in \ mathbb {N}}$${\ displaystyle p_ {1}}$${\ displaystyle p_ {2}}$${\ displaystyle p_ {1}}$${\ displaystyle p_ {3}}$${\ displaystyle 1 + 2 (r ^ {1} + r ^ {2})}$${\ displaystyle \ textstyle 1 + 2 \ sum _ {i = 1} ^ {\ infty} r ^ {i} = 3 + 2r}$${\ displaystyle 2M + 1}$${\ displaystyle M}$${\ displaystyle sv_ {1} t}$${\ displaystyle sv_ {2} v_ {3} t}$${\ displaystyle M}$${\ displaystyle sv_ {4} t}$

Outro exemplo não terminante baseado no algoritmo Euclidiano é dado por Backman & Huynh (2018) , onde eles também mostram que o pior caso de tempo de execução do algoritmo de Ford-Fulkerson em uma rede em números ordinais é . ${\ displaystyle G (V, E)}$${\ displaystyle \ omega ^ {\ Theta (| E |)}}$

Implementação em Python do algoritmo Edmonds – Karp

import collections

class Graph:
    """This class represents a directed graph using adjacency matrix representation."""

    def __init__(self, graph):
        self.graph = graph  # residual graph
        self.row = len(graph)

    def bfs(self, s, t, parent):
        """Returns true if there is a path from source 's' to sink 't' in
        residual graph. Also fills parent[] to store the path."""

        # Mark all the vertices as not visited
        visited = [False] * self.row

        # Create a queue for BFS
        queue = collections.deque()

        # Mark the source node as visited and enqueue it
        queue.append(s)
        visited[s] = True

        # Standard BFS loop
        while queue:
            u = queue.popleft()

            # Get all adjacent vertices of the dequeued vertex u
            # If an adjacent has not been visited, then mark it
            # visited and enqueue it
            for ind, val in enumerate(self.graph[u]):
                if (visited[ind] == False) and (val > 0):
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        # If we reached sink in BFS starting from source, then return
        # true, else false
        return visited[t]

    # Returns the maximum flow from s to t in the given graph
    def edmonds_karp(self, source, sink):

        # This array is filled by BFS and to store path
        parent = [-1] * self.row

        max_flow = 0  # There is no flow initially

        # Augment the flow while there is path from source to sink
        while self.bfs(source, sink, parent):

            # Find minimum residual capacity of the edges along the
            # path filled by BFS. Or we can say find the maximum flow
            # through the path found.
            path_flow = float("Inf")
            s = sink
            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            # Add path flow to overall flow
            max_flow += path_flow

            # update residual capacities of the edges and reverse edges
            # along the path
            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

Veja também

• Teorema de corte mínimo de fluxo máximo aproximado
• Roteamento de restrição de curvas

Notas

Referências

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Seção 26.2: O método Ford-Fulkerson". Introdução aos algoritmos (segunda edição). MIT Press e McGraw-Hill. pp. 651–664. ISBN 0-262-03293-7.
• George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Capítulo 8: Algoritmos de fluxo de rede". Algoritmos resumidos . Oreilly Media . pp. 226–250. ISBN 978-0-596-51624-6.
• Jon Kleinberg ; Éva Tardos (2006). "Capítulo 7: Extensões ao problema de fluxo máximo" . Projeto de algoritmos . Pearson Education. pp.  378–384 . ISBN 0-321-29535-8.
• Samuel Gutekunst (2009). ENGRI 1101 . Cornell University.
• Backman, Spencer; Huynh, Tony (2018). "Transfinite Ford – Fulkerson em uma rede finita". Computabilidade . 7 (4): 341–347. arXiv : 1504.04363 . doi : 10.3233 / COM-180082 . S2CID  15497138 .

links externos

• Um tutorial explicando o método Ford-Fulkerson para resolver o problema de fluxo máximo
• Outra animação Java
• Aplicativo Java Web Start

Mídia relacionada ao algoritmo de Ford-Fulkerson no Wikimedia Commons