Eu quero implementar o algoritmo Goldberg & Rao para encontrar um fluxo máximo em um gráfico. Meu problema é a etapa de atualização, na qual todos os documentos e relatórios afirmam "No gráfico resultante, encontre um fluxo de bloqueio ou um fluxo de valor Delta". Todos eles se referem à Goldberg & Tarjan para encontrar um fluxo de bloqueio. Há duas coisas que não entendo:
- Como devo encontrar um fluxo de valor Delta?
- Mas mais importante: como posso encontrar um fluxo de bloqueio?
Com relação às perguntas 2: li os dois artigos (o de Goldberg & Tarjan "Uma nova abordagem para o problema do fluxo máximo" e o de árvores dinâmicas - ambos não eram tão difíceis de entender). Todo artigo / relatório / livro sobre Goldberg & Rao se refere ao artigo de Goldberg & Tarjan e destaca que Goldberg & Rao não usa o algoritmo push / relabel, mas encontra fluxos de bloqueio. Mas, na minha opinião, Tarjan apenas explica o algoritmo push / re-label, não consigo encontrar nada sobre o bloqueio de fluxos.
T. Cormen, "Introdução aos algoritmos", 3ª edição
O algoritmo assintoticamente mais rápido até hoje para o problema de fluxo máximo, por Goldberg e Rao, é executado no tempo , onde . Esse algoritmo não usa o método push-re-label, mas baseia-se na localização de fluxos de bloqueio.
A. Goldberg e S. Rao, "Além da barreira de decomposição do fluxo" (o artigo original)
Usando o algoritmo de fluxo de bloqueio de Goldberg e Tarjan [1988], obtemos um limite .
fonte