Quiero implementar el algoritmo Goldberg & Rao para encontrar un flujo máximo en un gráfico. Mi problema es el paso de actualización donde cada documento e informe indica "En el gráfico resultante, encuentre un flujo de bloqueo o un flujo de valor Delta". Todos se refieren a Goldberg y Tarjan para encontrar un flujo de bloqueo. Hay dos cosas que no entiendo:
- ¿Cómo se supone que debo encontrar un flujo de valor Delta?
- Pero más importante: ¿cómo puedo encontrar un flujo de bloqueo?
Con respecto a las preguntas 2: leí los dos documentos (el de Goldberg y Tarjan "Un nuevo enfoque para el problema del flujo máximo" y el de los árboles dinámicos, ambos no fueron tan difíciles de entender). Cada artículo / informe / libro sobre Goldberg & Rao se refiere al artículo de Goldberg & Tarjan y destaca que Goldberg & Rao no utiliza el algoritmo push / reetiquetado sino que encuentra flujos de bloqueo. Pero en mi opinión, Tarjan solo explica el algoritmo push / relabel, no puedo encontrar nada sobre el bloqueo de flujos.
T. Cormen, "Introducción a los algoritmos", 3ª edición
El algoritmo asintóticamente más rápido hasta la fecha para el problema de flujo máximo, por Goldberg y Rao, se ejecuta en el tiempo , donde . Este algoritmo no utiliza el método push-relabel, sino que se basa en encontrar flujos de bloqueo.
A. Goldberg y S. Rao, "Más allá de la barrera de descomposición del flujo" (el documento original)
Usando el algoritmo de flujo de bloqueo de Goldberg y Tarjan [1988], obtenemos un límite .
fuente