Skip to content
Voltar aos resultados

Algoritmo Push-Relabel

Proposto por
Andrew V. Goldberg and Robert E. Tarjan
Ano
1988
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 Push-Relabel, desenvolvido por Andrew V. Goldberg e Robert E. Tarjan em 1988, é um método altamente eficiente para calcular o fluxo máximo em redes.

Diferentemente dos métodos de caminho aumentante, ele mantém um pré-fluxo e utiliza operações locais de "push" (empurrar) e globais de "relabel" (re-rotular) para direcionar o fluxo em direção ao sumidouro, alcançando uma complexidade de pior caso superior.

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

O algoritmo mantém uma "altura" ou "rótulo de distância" para cada nó e utiliza pré-fluxo (onde os nós podem temporariamente exceder a demanda do sumidouro). Ele repetidamente empurra o excesso de fluxo de nós com rótulos mais altos para vizinhos com rótulos mais baixos e re-rotula nós para criar caminhos para o sumidouro. A principal sacada é que, ao manter invariantes de altura e usar estruturas de dados eficientes, o algoritmo evita explorar o grafo inteiro repetidamente, como os métodos de caminho aumentante devem fazer. O algoritmo termina quando todo o excesso de fluxo atinge o sumidouro.

História

Goldberg e Tarjan publicaram seu algoritmo push-relabel em 1988, introduzindo um paradigma fundamentalmente diferente para o cálculo de fluxo máximo. Seu algoritmo alcançou complexidade de pior caso O(V³), uma melhoria em relação ao O(VE²) de Edmonds-Karp. Nas décadas seguintes, inúmeras variantes foram desenvolvidas, incluindo heurísticas de "gap" (Goldberg e Tarjan, 1990), regras de rótulo mais alto e as variantes mais recentes que alcançam desempenho empírico quase linear em redes do mundo real.

Quando usar

Aplique o algoritmo push-relabel para calcular o fluxo máximo em grandes redes densas onde os métodos de caminho aumentante se tornam ineficientes. É particularmente eficaz para redes com milhares ou milhões de arestas. Use-o quando precisar de desempenho garantido em tempo polinomial e quiser aproveitar estruturas de dados modernas. Para redes esparsas ou fins educacionais, os métodos de caminho aumentante podem ser mais simples de entender e implementar.

Limitações e considerações

  • Mais complexo de entender e implementar do que os métodos de caminho aumentante
  • Requer manuseio cuidadoso de estruturas de dados (listas de descarga, heurísticas de "gap") para desempenho ótimo
  • A complexidade de pior caso ainda é maior do que alguns algoritmos especializados para classes de grafos especiais
  • Compreensão menos intuitiva do processo de solução em comparação com os caminhos aumentantes

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

  • Complexidade de tempo de pior caso superior: O(V³) ou O(V²√E) com heurística de "gap"
  • Altamente eficiente na prática, especialmente para redes grandes e densas
  • A localidade das operações (push/relabel) permite um bom desempenho de cache
  • Adequado para paralelização e implementações distribuídas
  • Múltiplas variantes de implementação para diferentes estruturas de problemas

Aplicações

  • Roteamento de rede: cálculo do rendimento máximo em grandes redes de comunicação
  • Processamento de imagem: uso de fluxo máximo para segmentação de imagem e aplicações de "matting"
  • Otimização de companhias aéreas: determinação do fluxo máximo de passageiros através de redes de roteamento complexas
  • Análise de redes elétricas: cálculo da capacidade máxima de transmissão de energia em redes elétricas
  • Gestão da cadeia de suprimentos: otimização do fluxo de produtos através de redes de distribuição de múltiplos níveis
  • Redes biológicas: análise do fluxo máximo em redes metabólicas e de interação proteica

Como funciona

Como funciona

1

Defina a altura da fonte como o número de vértices, e todas as outras alturas como zero. Sature todas as arestas que saem da fonte, criando um pré-fluxo inicial (excesso nos nós vizinhos).

2

Selecione repetidamente um nó ativo (com excesso de fluxo) e empurre o excesso para um vizinho de altura inferior ou re-rotule o nó para aumentar sua altura. Use estratégias de seleção e operações de descarga eficientes para minimizar as iterações.

3

Continue até que não restem nós ativos, momento em que todo o pré-fluxo foi resolvido em um fluxo máximo da fonte para o sumidouro.

Erros comuns

  • Implementar incorretamente as atualizações de altura ou operações de "push" levando a fluxos não máximos
  • Negligenciar o uso de heurísticas de "gap" e seleção eficiente de nós, resultando em desempenho prático insatisfatório
  • Não conseguir manter adequadamente o invariante de pré-fluxo (excesso nos nós e restrições de capacidade nas arestas)

Perguntas frequentes

Qual a diferença entre pré-fluxo e fluxo?

O pré-fluxo permite temporariamente que os nós retenham excesso de fluxo (o fluxo de entrada menos o fluxo de saída pode ser positivo), enquanto o fluxo verdadeiro deve ser conservado em todos os nós, exceto na fonte e no sumidouro. O algoritmo termina quando o pré-fluxo se torna um fluxo válido.

Qual o propósito da função de altura?

As alturas criam uma medida de quase-distância: o fluxo só pode ser empurrado "ladeira abaixo" (de alturas mais altas para mais baixas), evitando ciclos desnecessários e garantindo a terminação. As alturas são aumentadas através do re-rotulamento para criar novos caminhos quando necessário.

O que é a heurística de "gap" e por que ela é importante?

A heurística de "gap" detecta quando nenhum nó tem uma altura em um determinado intervalo, indicando que alguns nós não conseguem alcançar o sumidouro. Esses nós e seu excesso são rapidamente identificados e processados, melhorando significativamente o desempenho prático.

Como o push-relabel se compara na prática ao Edmonds-Karp?

O push-relabel tem uma complexidade de pior caso melhor e geralmente supera o Edmonds-Karp em grandes redes, mas para redes pequenas ou grafos esparsos, o Edmonds-Karp pode ser mais simples de implementar com desempenho competitivo.

Métodos relacionados

Fontes

  1. Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.

    Abrir referência DOI
    Copiado.
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    Abrir referência da publicação
    Copiado.