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
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
Inicializar o grafo residual com capacidades iguais às capacidades originais das arestas e fluxo zero em todas as arestas.
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.
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
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
Abrir referência DOICopiado.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Copiado.