Skip to content
Voltar aos resultados

Algoritmo de Ford-Fulkerson

Proposto por
Lester R. Ford and Delbert R. Fulkerson
Ano
1956
Tipo
algorithm
Família
Graph Algorithms

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

O Algoritmo de Ford-Fulkerson, desenvolvido por Lester R. Ford e Delbert R. Fulkerson em 1956, é um método fundamental para calcular o fluxo máximo em uma rede de fluxo.

Ele encontra a quantidade máxima de fluxo que pode ser enviada de uma origem para um destino através de um grafo direcionado com restrições de capacidade nas arestas.

A intuição por trás do método

O algoritmo funciona encontrando repetidamente caminhos de aumento da origem ao destino através da rede residual, onde cada aresta tem capacidade restante. Cada caminho contribui com um fluxo adicional igual à sua capacidade de gargalo (a aresta com a menor capacidade restante no caminho). O processo continua até que não existam mais caminhos de aumento, momento em que o fluxo máximo é alcançado. A percepção chave é o teorema do corte mínimo e do fluxo máximo: o fluxo máximo é igual à capacidade mínima de corte na rede.

História

Ford e Fulkerson introduziram o problema do fluxo máximo e seu algoritmo seminal em 1956. O trabalho foi revolucionário, estabelecendo tanto um método algorítmico quanto o celebrado teorema do fluxo máximo-corte mínimo. Edmonds e Karp (1972) melhoraram a complexidade no pior caso usando busca em largura para a seleção de caminhos. Avanços subsequentes por Dinic, Karzanov e outros levaram a algoritmos ainda mais rápidos, mas o método de Ford-Fulkerson permanece um algoritmo clássico e pedagogicamente valioso na ciência da computação.

Quando usar

Aplicar o algoritmo de Ford-Fulkerson para encontrar o fluxo máximo em redes de fluxo direcionadas ou não direcionadas com capacidades inteiras positivas. Ele funciona bem para redes de tamanho pequeno a médio e fornece uma compreensão intuitiva dos conceitos de fluxo em rede. Para redes muito grandes ou quando fluxos integrais são necessários, considere o algoritmo de Edmonds-Karp (usando BFS) ou o algoritmo de Dinic para melhor desempenho no pior caso. Use-o quando a compreensão do comportamento do algoritmo for tão importante quanto a velocidade.

Limitações e considerações

  • A complexidade de tempo depende dos valores de capacidade (não polinomial em geral; pode ser exponencial com capacidades irracionais)
  • Pode não convergir se as capacidades forem irracionais (requer implementação cuidadosa com aritmética racional)
  • Menos eficiente que algoritmos especializados como Edmonds-Karp ou Dinic em redes grandes
  • Sensível à ordem de seleção do caminho de aumento

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Abordagem simples e intuitiva baseada em caminhos de aumento
  • Solução ótima garantida quando as capacidades são racionais ou inteiras
  • Eficiente para redes com pequenas capacidades inteiras
  • Forma a base teórica para a compreensão da dualidade fluxo máximo-corte mínimo
  • Funciona com grafos direcionados e não direcionados

Aplicações

  • Roteamento de rede: maximizar a taxa de transferência de dados de origem para destino em redes de comunicação
  • Redes de transporte: determinar a capacidade máxima de carga entre cidades considerando restrições de estradas e ferrovias
  • Correspondência bipartida: encontrar correspondências máximas em grafos bipartidos construindo redes de fluxo
  • Segmentação de imagem: usar algoritmos de fluxo máximo para particionar imagens em primeiro plano e fundo
  • Agendamento de companhias aéreas: otimizar o roteamento de aeronaves para maximizar o fluxo de passageiros através de redes hub-and-spoke
  • Análise de proteínas: calcular o fluxo máximo em redes biológicas para entender as vias de interação

Como funciona

Como funciona

1

Inicializar o grafo residual com capacidades iguais às capacidades originais das arestas e fluxo zero em todas as arestas.

2

Encontrar um caminho de aumento da origem ao destino no grafo residual usando busca em profundidade ou em largura, calcular a capacidade mínima ao longo do caminho e adicionar esse fluxo a todas as arestas no caminho, reduzindo suas capacidades residuais.

3

Repetir a ampliação até que nenhum caminho de aumento exista no grafo residual; o fluxo total acumulado é o fluxo máximo.

Erros comuns

  • Escolher caminhos de aumento ruins que resultam em convergência lenta ou resultados incorretos
  • Falhar em atualizar corretamente as capacidades residuais ou adicionar arestas reversas para desfazer o fluxo
  • Usar divisão inteira ou aritmética de ponto flutuante quando a aritmética exata é necessária para a correção

Perguntas frequentes

O que é o teorema do fluxo máximo-corte mínimo?

O teorema afirma que o fluxo máximo da origem ao destino é igual à capacidade mínima de qualquer corte que separa a origem do destino. Isso fornece tanto uma visão teórica quanto um método de verificação para algoritmos de fluxo.

Por que o algoritmo às vezes converge lentamente?

Com seleções de caminhos infelizes, o algoritmo pode aumentar apenas uma unidade de fluxo por iteração, mesmo quando aumentos maiores são possíveis. Usar busca em largura (Edmonds-Karp) garante convergência em tempo polinomial.

Como o algoritmo lida com arestas não direcionadas?

Substitua cada aresta não direcionada por duas arestas direcionadas em direções opostas, ambas com a mesma capacidade. O algoritmo então encontra o fluxo na rede direcionada.

Qual é a diferença entre fluxo em uma aresta e capacidade residual?

O fluxo em uma aresta representa a quantidade de material enviado por ela, enquanto a capacidade residual é a capacidade restante disponível. A capacidade residual diminui à medida que o fluxo aumenta, e as arestas reversas rastreiam a capacidade de desfazer o fluxo.

Métodos relacionados

Fontes

  1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.

    Abrir referência DOI
    Copiado.
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

    ISBN: 978-0-262-03384-8
    Copiado.