Algoritmo de flujo máximo push-reetiquetado

En la optimización matemática , el algoritmo push-relabel (alternativamente, algoritmo de preflujo-push ) es un algoritmo para calcular los flujos máximos en una red de flujo . El nombre "empujar-volver a etiquetar" proviene de las dos operaciones básicas utilizadas en el algoritmo. A lo largo de su ejecución, el algoritmo mantiene un "preflujo" y lo convierte gradualmente en un flujo máximo moviendo el flujo localmente entre nodos vecinos utilizando operaciones de empuje bajo la guía de una red admisible mantenida por operaciones de reetiquetado . En comparación, el algoritmo Ford-Fulkersonrealiza aumentos globales que envían el flujo siguiendo rutas desde la fuente hasta el sumidero. ^[1]

El algoritmo de empujar-volver a etiquetar se considera uno de los algoritmos de flujo máximo más eficientes. El algoritmo genérico tiene una complejidad de tiempo $O$ $($ $V$ $2$ $E$ $)$ fuertemente polinomial , que es asintóticamente más eficiente que el algoritmo $O$ $($ $VE$ $2$ $)$ Edmonds-Karp . ^[2] Las variantes específicas de los algoritmos logran complejidades de tiempo aún menores. La variante basada en la regla de selección de nodo de etiqueta más alta tiene una complejidad de tiempo $O$ $($ $V$ $2$ $\sqrt$ $E$ $)$ y generalmente se considera como el punto de referencia para los algoritmos de flujo máximo. ^[3]^[4] La complejidad temporal subcúbica $O (VE log (V 2 / E))$ se puede lograr utilizando árboles dinámicos , aunque en la práctica es menos eficiente. ^[2]

El algoritmo de inserción y re-etiqueta se ha ampliado para calcular los flujos de costo mínimo . ^[5] La idea de las etiquetas de distancia ha llevado a un algoritmo de ruta de aumento más eficiente, que a su vez puede incorporarse nuevamente al algoritmo de empujar-volver a etiquetar para crear una variante con un rendimiento empírico aún mayor. ^[4]^[6]

Historia

El concepto de preflujo fue diseñado originalmente por Alexander V. Karzanov y se publicó en 1974 en Soviet Mathematical Dokladi 15. Este algoritmo de preflujo también utilizó una operación de empuje; sin embargo, utilizó distancias en la red auxiliar para determinar dónde empujar el flujo en lugar de un sistema de etiquetado. ^[2]^[7]

El algoritmo push-relabel fue diseñado por Andrew V. Goldberg y Robert Tarjan . El algoritmo se presentó inicialmente en noviembre de 1986 en STOC '86: Actas del decimoctavo simposio anual de ACM sobre teoría de la computación, y luego oficialmente en octubre de 1988 como un artículo en el Journal of the ACM. Ambos artículos detallan una forma genérica del algoritmo que termina en $O (V 2 E)$ junto con una implementación secuencial $O (V 3)$ , un $O (VE log (V 2 / E))$ implementación mediante árboles dinámicos e implementación paralela / distribuida. ^[2]^[8] A explicado en ^[9] Goldberg-Tarjan introdujo etiquetas de distancia incorporándolas en el algoritmo de flujo máximo paralelo de Yossi Shiloach y Uzi Vishkin . ^[10]

Conceptos

Definiciones y notaciones

Dejar:

$G = (V, E)$ sea una red con función de capacidad $c : V \times V \to ℝ \infty$ ,
$F = (G, c, s, t)$ una red de flujo , donde $s \in V$ y $t \in V$ se eligenvértices fuente y sumidero respectivamente,
$f : V \times V \to ℝ$ denotan un pre-flujo en $F$ ,
$x f : V \to ℝ$ denota lafunción de exceso con respecto al flujo $f$ , definido por $x f (u) = \sum v \in V f (v, u) - \sum v \in V f (u, v)$ ,
$c f : V \times V \to ℝ \infty$ denota la función de capacidad residual con respecto al flujo $f$ , definido por $c f (e) = c (e) - f (e)$ ,
$E f \subset E$ siendo los bordes donde $f < c$ ,

y

$G f (V, E f)$ denota la red residual de $G$ con respecto al flujo $f$ .

El algoritmo de empujar-volver a etiquetar utiliza una función de etiquetado válido de entero no negativo que hace uso de etiquetas de distancia , o alturas , en los nodos para determinar qué arcos deben seleccionarse para la operación de empuje. Esta función de etiquetado se denota por $𝓁: V \to ℕ$ . Esta función debe cumplir las siguientes condiciones para ser considerada válida:

Etiquetado válido :

𝓁 (u) \leq 𝓁 (v) + 1

para todo

(u, v) \in E f

Condición de la fuente :

𝓁 (s) = | V |

Conservación del fregadero :

𝓁 (t) = 0

En el algoritmo, los valores de la etiqueta de $s$ y $t$ son fijos. $𝓁 (u)$ es un límite inferior de la distancia no ponderada de $u$ a $t$ en $G f$ si $t$ es alcanzable desde $u$ . Si $u$ se ha desconectado de $t$ , entonces $𝓁 (u) - | V |$ es un límite inferior de la distancia no ponderada de $u$ a $s$ . Como resultado, si existe una función de etiquetado válida, no hay rutas $s - t$ en $G f$ porque ninguno de estos caminos puede ser más largo que $| V | - 1$ .

Un arco $(u, v) \in E f$ se considera admisible si $𝓁 (u) = 𝓁 (v) + 1$ . La red admisible $G̃ f (V, Ẽ f)$ está compuesta por el conjunto de arcos $e \in E f$ que son admisibles. La red admisible es acíclica.

Operaciones

Inicialización

El algoritmo comienza creando un gráfico residual, inicializando los valores de preflujo a cero y realizando un conjunto de operaciones de empuje de saturación en arcos residuales que salen de la fuente, $( s , v ) donde v ∈ V \ { s }$ . De manera similar, las etiquetas se inicializan de manera que la etiqueta en la fuente sea el número de nodos en el gráfico, $𝓁 (s) = | V |$ , y todos los demás nodos reciben una etiqueta de cero. Una vez que se completa la inicialización, el algoritmo realiza repetidamente las operaciones de inserción o reetiquetado contra los nodos activos hasta que no se pueda realizar ninguna operación aplicable.

Empujar

La operación de empuje se aplica a un arco externo admisible $(u, v)$ de un nodo activo $u$ en $G f$ . Mueve $min {x f (u), c f (u, v)}$ unidades de flujo de $u$ a $v$ .

empujar (u, v): afirmar x _f [u]> 0 y 𝓁 [u] == 𝓁 [v] + 1 Δ = mínimo (x _f [u], c [u] [v] - f [u] [v]) f [u] [v] + = Δ f [v] [u] - = Δ x _f [u] - = Δ x _f [v] + = Δ

Una operación de empuje que hace que $f (u, v)$ alcance $c (u, v)$ se llama empuje de saturación ya que usa toda la capacidad disponible del arco residual. De lo contrario, todo el exceso en el nodo se empuja a través del arco residual. Esto se llama impulso insaturado o no saturante .

Reetiquetar

La operación de reetiquetado se aplica a un nodo activo $u$ sin ningún arco externo admisible en $G f$ . Modifica $𝓁 (u)$ para que sea el valor mínimo tal que se cree un arco $externo$ admisible. Tenga en cuenta que esto siempre aumenta $𝓁 (u)$ y nunca crea un arco empinado, que es un arco $(u, v)$ tal que $c f (u, v)> 0$ y $𝓁 (u)> 𝓁 (v) + 1$ .

reetiquetar (u): afirmar x _f [u]> 0 y 𝓁 [u] <= 𝓁 [v] para todo v tal que c _f [u] [v]> 0 𝓁 [u] = 1 + min (𝓁 [v] para todo v tal que c _f [u] [v]> 0)

Efectos de empujar y volver a etiquetar

Después de una operación de empujar o volver a etiquetar, $𝓁$ sigue siendo una función de etiquetado válida con respecto a $f$ .

Para una operación de empuje en un arco admisible $(u, v)$ , puede agregar un arco $(v, u)$ a $E f$ , donde $𝓁 (v) = 𝓁 (u) - 1 \leq 𝓁 (u) + 1$ ; también puede eliminar el arco $(u, v)$ de $E f$ , donde efectivamente elimina la restricción $𝓁 (u) \leq 𝓁 (v) + 1$ .

Para ver que una operación de reetiquetado en el nodo $u$ preserva la validez de $𝓁 (u)$ , observe que esto está garantizado trivialmente por definición para los arcos externos de u en $G f$ . Para los arcos $internos$ de $u$ en $G f$ , el aumento de $𝓁 (u)$ solo puede satisfacer las restricciones de manera menos estricta, no violarlas.

El algoritmo genérico de inserción y re-etiqueta

El algoritmo genérico de reenvío y reetiquetado se utiliza solo como prueba de concepto y no contiene detalles de implementación sobre cómo seleccionar un nodo activo para las operaciones de reenvío y reetiquetado. Esta versión genérica del algoritmo terminará en $O (V 2 E)$ .

Dado que $𝓁 (s) = | V |$ , $𝓁 (t) = 0$ , y no hay caminos más largos que $| V | - 1$ en $G f$ , para que $𝓁 (s)$ satisfagan las condiciones de etiquetado válidas, $s$ debe desconectarse de $t$ . En la inicialización, el algoritmo cumple este requisito creando un $preflujo$ $f$ que satura todos los arcos $externos$ de $s$ , después del cual $𝓁 (v) = 0$ es trivialmente válido para todos $v ∈ V \ { s, t }$ . Después de la inicialización, el algoritmo ejecuta repetidamente una operación de inserción o reetiquetado aplicable hasta que no se apliquen tales operaciones, momento en el que el preflujo se ha convertido en un flujo máximo.

genérico-push-relabel (G, c, s, t): crear un preflujo f que sature todos los arcos externos de s sea 𝓁 [s] = | V | deje 𝓁 [v] = 0 para todo v ∈ V \ {s} mientras haya una operación de inserción o reetiquetado aplicable . ejecutar la operación

Exactitud

El algoritmo mantiene la condición de que $𝓁$ sea un etiquetado válido durante su ejecución. Esto se puede comprobar si se examinan los efectos de las operaciones de inserción y reetiquetado en la función de etiqueta $𝓁$ . La operación de reetiquetado aumenta el valor de la etiqueta por el mínimo asociado más uno que siempre satisfará la $restricción 𝓁 (u) \leq 𝓁 (v) + 1$ . La operación de empuje puede enviar flujo de $u$ a $v$ si $𝓁 (u) = 𝓁 (v) + 1$ . Esto puede agregar $(v, u)$ a $G f$ y puede eliminar $(u, v)$ de $G f$ . La adición de $(v, u)$ a $G f$ no afectará el etiquetado válido ya que $𝓁 (v) = 𝓁 (u) - 1$ . La eliminación de $(u, v)$ de $G f$ elimina la restricción correspondiente ya que la propiedad de etiquetado válida $𝓁 (u) \leq 𝓁 (v) + 1$ solo se aplica a los arcos residuales en $G f$ .^[8]

Si un preflujo $f$ y un etiquetado válido $𝓁$ para $f$ existe, entonces no hay trayectoria de aumento de $s$ a $t$ en el residual gráfico $G f$ . Esto se puede demostrar por la contradicción basada en las desigualdades que surgen en la función de etiquetado cuando se supone que existe un camino de aumento. Si el algoritmo termina, entonces todos los nodos en $V \ { s , t }$ no están activos. Esto significa que todos $v ∈ V \ { s , t }$ no tienen exceso de flujo, y sin exceso el preflujo $f$ obedece a la restricción de conservación del caudal y puede considerarse un caudal normal. Este flujo es el flujo máximo de acuerdo con el flujo max teorema min de corte ya que no hay trayectoria de aumento de $s$ a $t$ . ^[8]

Por lo tanto, el algoritmo devolverá el flujo máximo al finalizar.

Complejidad del tiempo

Para limitar la complejidad temporal del algoritmo, debemos analizar el número de operaciones de inserción y reetiquetado que se producen dentro del bucle principal. Los números de operaciones de reetiquetado, empuje saturado y empuje no saturado se analizan por separado.

En el algoritmo, la operación de reetiquetado se puede realizar como máximo $(2 | V | - 1) (| V | - 2) <2 | V | 2$ veces. Esto se debe a que el valor de etiquetado $𝓁 (u)$ para cualquier nodo u nunca puede disminuir, y el valor de etiqueta máximo es como máximo $2 | V | - 1$ para todos los nodos. Esto significa que la operación de reetiquetado podría potencialmente realizarse $2 | V | - 1$ veces para todos los nodos $V \ { s , t }$ (es decir, $| V | - 2$ ). Esto da como resultado un límite de $O (V 2)$ para la operación de reetiquetado.

Cada empuje de saturación en un arco admisible $(u, v)$ elimina el arco de $G f$ . Para el arco a ser reinsertado en $G f$ para otro empuje de saturación, $v$ primero debe vuelve a etiquetar, seguida de un empuje sobre el arco $(v, u)$ , entonces $u$ debe ser re-etiquetado. En el proceso, $𝓁 (u)$ aumenta en al menos dos. Por lo tanto, hay $O (V)$ saturación empuja en $(u, v)$ , y el número total de pulsaciones de saturación es como máximo $2 | V || E |$ . Esto da como resultado un límite de tiempo de $O (VE)$ para las operaciones de empuje de saturación.

Limitar el número de impulsos no saturados se puede lograr mediante un argumento potencial . Usamos la función potencial $Φ = \sum [u \in V \land x f (u)> 0] 𝓁 (u)$ (es decir, $Φ$ es la suma de las etiquetas de todos los nodos activos). Es obvio que $Φ$ es $0$ inicialmente y permanece no negativo durante la ejecución del algoritmo. Tanto las reetiquetas como las pulsaciones de saturación pueden aumentar $Φ$ . Sin embargo, el valor de $Φ$ debe ser igual a 0 al finalizar, ya que no pueden quedar nodos activos restantes al final de la ejecución del algoritmo. Esto significa que durante la ejecución del algoritmo, los empujes no saturados deben compensar la diferencia de las operaciones de reetiquetado y de saturación para que $Φ$ termine con un valor de 0. La operación de reetiquetado puede aumentar $Φ$ como máximo $(2 | V | - 1) (| V | - 2)$ . Un empuje saturado en $(u, v)$ activa $v$ si estaba inactivo antes del empuje, aumentando $Φ$ como máximo $2 | V | - 1$ . Por lo tanto, la contribución total de todas las operaciones de saturación de empuje a $Φ$ es como máximo $(2 | V | - 1) (2 | V || E |)$ . Una pulsación no saturada en $(u, v)$ siempre desactiva $u$ , pero también puede activar $v$ como en una pulsación saturada. Como resultado, disminuye $Φ$ en al menos $𝓁 (u) - 𝓁 (v) = 1$ . Dado que las reetiquetas y los impulsos de saturación aumentan $Φ$ , el número total de impulsos no saturados debe compensar la diferencia de $(2 | V | - 1) (| V | - 2) + (2 | V | - 1) (2 | V || E |) \leq 4 | V | 2 | E |$ . Esto da como resultado un límite de tiempo de $O (V 2 E)$ para las operaciones de empuje no saturadas.

En resumen, el algoritmo ejecuta $O (V 2)$ reetiquetas, $O (VE)$ empujes saturantes y $O (V 2 E)$ empujes no saturados. Las estructuras de datos se pueden diseñar para seleccionar y ejecutar una operación aplicable en $O (1)$ tiempo. Por tanto, la complejidad temporal del algoritmo es $O (V 2 E)$ . ^[1]^[8]

Ejemplo

La siguiente es una ejecución de muestra del algoritmo genérico de reenvío de etiquetas, como se definió anteriormente, en el siguiente diagrama de flujo de red simple.

Gráfico de red de caudal máximo final

En el ejemplo, los h y e valores denotan la etiqueta $𝓁$ y el exceso de $x f$ , respectivamente, del nodo durante la ejecución del algoritmo. Cada gráfico residual en el ejemplo solo contiene los arcos residuales con una capacidad mayor que cero. Cada gráfico residual puede contener múltiples iteraciones del ciclo de operación de ejecución .

Operación (es) del algoritmo	Gráfico residual
Inicialice el gráfico residual estableciendo el preflujo en valores 0 e inicializando el etiquetado.
El empuje de saturación inicial se realiza en todos los arcos de preflujo fuera de la fuente, $s$ .
El nodo $a$ se vuelve a etiquetar para empujar su exceso de flujo hacia el fregadero, $t$ . El exceso en $un$ continuación se empuja a $b$ a continuación, $d$ en dos empujes posteriores saturantes; que todavía deja $un$ exceso.

Una vez más, $a$ se vuelve a etiquetar para empujar su exceso a lo largo de su último residuo positivo restante (es decir, empujar el exceso hacia $s$ ). A continuación, el nodo $a$ se elimina del conjunto de nodos activos.

Relabel $b$ y luego empujar su exceso de $t$ y $c$ .
Vuelva a etiquetar $cy$ luego empuje su exceso a $d$ .
Vuelva a etiquetar $d$ y luego empuje su exceso a $t$ .
Esto deja al nodo $b$ como el único nodo activo restante, pero no puede empujar su exceso de flujo hacia el sumidero. Vuelva a etiquetar $by$ luego empuje su exceso hacia la fuente, $s$ , a través del nodo $a$ .

Empuje la última parte del exceso en $una$ vuelta a la fuente, $s$ . No quedan nodos activos restantes. El algoritmo termina y devuelve el flujo máximo del gráfico (como se ve arriba).

El ejemplo (pero con un flujo inicial de 0) se puede ejecutar aquí de forma interactiva.

Implementaciones prácticas

Mientras que el algoritmo genérico de inserción y reetiquetado tiene una complejidad de tiempo $O (V 2 E)$ , las implementaciones eficientes logran $O (V 3)$ o una menor complejidad de tiempo al hacer cumplir las reglas adecuadas en la selección de las operaciones de inserción y reetiquetado aplicables. El rendimiento empírico se puede mejorar aún más mediante heurística.

Estructura de datos de "arco de corriente" y operación de descarga

La estructura de datos de "arco de corriente" es un mecanismo para visitar los vecinos de entrada y salida de un nodo en la red de flujo en un orden circular estático. Si se crea una lista de vecinos enlazados individualmente para un nodo, la estructura de datos puede ser tan simple como un puntero en la lista que recorre la lista y se rebobina al principio cuando termina.

Basándose en la estructura de datos de "arco de corriente", se puede definir la operación de descarga. Una operación de descarga se aplica a un nodo activo y empuja repetidamente el flujo desde el nodo hasta que se vuelve inactivo, volviéndolo a etiquetar según sea necesario para crear arcos admisibles en el proceso.

descarga (u): mientras x _f [u]> 0 hacer  si el arco de corriente [u] se ha escapado del final de los vecinos [u] entonces volver a etiquetar (u) rebobinar el arco de corriente [u] de lo contrario,  sea (u, v) = current-arc [u] si (u, v) es admisible entonces empujar (u, v) deje que current-arc [u] apunte al próximo vecino de u

Reglas de selección de nodos activos

La definición de la operación de descarga reduce el algoritmo de empujar-volver a etiquetar a seleccionar repetidamente un nodo activo para descargar. Dependiendo de la regla de selección, el algoritmo presenta diferentes complejidades de tiempo. En aras de la brevedad, no hacemos caso de $s$ y $t$ cuando se hace referencia a los nodos en la siguiente discusión.

Regla de selección FIFO

El algoritmo FIFO push-reetiquetado ^[2] organiza los nodos activos en una cola. Los nodos activos iniciales se pueden insertar en orden arbitrario. El algoritmo siempre elimina el nodo al principio de la cola para su descarga. Siempre que un nodo inactivo se vuelve activo, se agrega al final de la cola.

El algoritmo tiene una complejidad de tiempo $O (V 3)$ .

Regla de selección de etiquetado al frente

El algoritmo de reetiquetado al frente ^[1] organiza todos los nodos en una lista enlazada y mantiene el invariante de que la lista está ordenada topológicamente con respecto a la red admisible. El algoritmo escanea la lista de adelante hacia atrás y realiza una operación de descarga en el nodo actual si está activo. Si el nodo se vuelve a etiquetar, se mueve al principio de la lista y el análisis se reinicia desde el principio.

El algoritmo también tiene una complejidad de tiempo $O (V 3)$ .

Regla de selección de etiquetas más alta

El algoritmo de inserción y reetiquetado de etiqueta más alta ^[11] organiza todos los nodos en depósitos indexados por sus etiquetas. El algoritmo siempre selecciona un nodo activo con la etiqueta más grande para descargar.

El algoritmo tiene una complejidad de tiempo $O (V 2 \sqrt E)$ . Si en su lugar se usa la regla de selección de la etiqueta más baja, la complejidad del tiempo se convierte en $O (V 2 E)$ . ^[3]

Técnicas de implementación

Aunque en la descripción del algoritmo genérico de inserción y reetiquetado anterior, $𝓁 (u)$ se establece en cero para cada nodo u distinto de $s$ y $t$ al principio, es preferible realizar una búsqueda hacia atrás en amplitud primero desde $t$ para calcular el valor exacto etiquetas. ^[2]

El algoritmo generalmente se divide en dos fases. La fase uno calcula un preflujo máximo descargando solo los nodos activos cuyas etiquetas están por debajo de $n$ . La fase dos convierte el preflujo máximo en un flujo máximo devolviendo el exceso de flujo que no puede alcanzar $t$ a $s$ . Se puede demostrar que la fase dos tiene una complejidad de tiempo $O (VE)$ independientemente del orden de las operaciones de inserción y reetiquetado y, por lo tanto, está dominada por la fase uno. Alternativamente, se puede implementar mediante descomposición de flujo. ^[9]

La heurística es fundamental para mejorar el rendimiento empírico del algoritmo. ^[12] Dos heurísticas de uso común son la heurística de brecha y la heurística de reetiquetado global. ^[2]^[13] La heurística de huecos detecta huecos en la función de etiquetado. Si hay una etiqueta 0 <𝓁 ' <| V | para el cual no hay un nodo $u$ tal que $𝓁 (u) = 𝓁'$ , entonces cualquier nodo $u$ con $𝓁' <𝓁 (u) <| V |$ se ha desconectado de $ty$ se puede volver a etiquetar como $(| V | + 1)$ inmediatamente. La heurística de reetiquetado global realiza periódicamente una búsqueda hacia atrás en amplitud desde $t$ en $G f$ para calcular las etiquetas exactas de los nodos. Ambas heurísticas omiten operaciones de reetiquetado inútiles, que son un cuello de botella del algoritmo y contribuyen a la ineficacia de los árboles dinámicos. ^[4]

Implementaciones de muestra

Implementación de C

#include  <stdlib.h>#include  <stdio.h>#define NODES 6 #define MIN (X, Y) ((X) <(Y)? (X): (Y)) #define INFINITE 10000000vacío  push ( const  int  *  const  *  C ,  int  **  F ,  int  * exceso ,  int  u ,  int  v )  {  int  enviar  =  MIN ( exceso [ u ],  C [ u ] [ v ]  -  F [ u ] [ v ]);  F [ u ] [ v ]  + =  enviar ;  F[ v ] [ u ]  - =  enviar ;  exceso [ u ]  - =  enviar ;  exceso [ v ]  + =  enviar ; }void  relabel ( const  int  *  const  *  C ,  const  int  *  const  *  F ,  int  * height ,  int  u )  {  int  v ;  int  MIN_HEIGHT  =  INFINITE ;  para  ( v  =  0 ;  v  <  NODOS ;  v ++ )  {  si  ( C [ u ] [ v ]  - F [ u ] [ v ]  >  0 )  {  min_height  =  MIN ( min_height ,  altura [ v ]);  altura [ u ]  =  altura_mín  +  1 ;  }  } }; descarga vacía ( const  int  *  const  *  C ,  int  **  F ,  int  * exceso ,  int  * altura ,  int  * visto ,  int  u )  {  while  ( exceso [ u ]  >  0 )  {  if  ( visto [ u ]  <  NODOS )  {  int  v  =  visto [ u];  if  (( C [ u ] [ v ]  -  F [ u ] [ v ]  >  0 )  &&  ( altura [ u ]  >  altura [ v ]))  {  empujar ( C ,  F ,  exceso ,  u ,  v );  }  else  {  visto [ u ]  + =  1 ;  }  }  else  {  volver a etiquetar( C ,  F ,  altura ,  u );  visto [ u ]  =  0 ;  }  } }void  moveToFront ( int  i ,  int  * A )  {  int  temp  =  A [ i ];  int  n ;  para  ( n  =  i ;  n  >  0 ;  n - )  {  A [ n ]  =  A [ n -1 ];  }  A [ 0 ]  =  temp ; }int  pushRelabel ( const  int  *  const  *  C ,  int  **  F ,  int  fuente ,  int  sumidero )  {  int  * exceso ,  * altura ,  * lista ,  * visto ,  i ,  p ; exceso  =  ( int  * )  calloc ( NODES ,  sizeof ( int ));  altura  =  ( int  * )  calloc ( NODES ,  sizeof ( int ));  visto  =  ( int  * )  calloc ( NODOS ,  tamaño de ( int )); lista  =  ( int  * )  calloc (( NODOS -2 ),  tamaño de ( int )); for  ( i  =  0 ,  p  =  0 ;  i  <  NODES ;  i ++ ) {  if  (( i  ! =  source )  &&  ( i  ! =  sink ))  {  list [ p ]  =  i ;  p ++ ;  }  } altura [ fuente ]  =  NODOS ;  exceso [ fuente ]  =  INFINITO ;  para  ( i  =  0 ;  i  <  NODOS ;  i ++ )  empujar ( C ,  F ,  exceso ,  fuente ,  i ); p  =  0 ;  while  ( p  <  NODOS  -  2 )  {  int  u  =  lista [ p ];  int  old_height  =  altura [ u ];  descarga ( C ,  F ,  exceso ,  altura ,  visto ,  u );  if  ( altura [ u ]  >  altura_antigua )  {  moveToFront ( p , lista );  p  =  0 ;  }  más  {  p  + =  1 ;  }  }  int  maxflow  =  0 ;  para  ( i  =  0 ;  i  <  NODES ;  i ++ )  maxflow  + =  F [ fuente ] [ i ]; gratis ( lista ); libre ( visto );  libre ( altura );  libre ( exceso ); return  maxflow ; }nulo  printMatrix ( const  int  *  const  *  M )  {  int  i ,  j ;  para  ( i  =  0 ;  i  <  NODOS ;  i ++ )  {  para  ( j  =  0 ;  j  <  NODOS ;  j ++ )  printf ( "% d \ t " , M [ i ] [ j ]);  printf (" \ n " );  } }int  main ( void )  {  int  ** flujo ,  ** capacidades ,  i ;  flujo  =  ( int  ** )  calloc ( NODOS ,  tamaño de ( int * ));  capacidades  =  ( int  ** )  calloc ( NODES ,  sizeof ( int * ));  para  ( i  =  0 ;  i  <  NODOS ; i ++ )  {  flujo [ i ]  =  ( int  * )  calloc ( NODES ,  sizeof ( int ));  capacidades [ i ]  =  ( int  * )  calloc ( NODES ,  sizeof ( int ));  } //  Capacidades del gráfico de muestra [ 0 ] [ 1 ]  =  2 ;  capacidades [ 0 ] [ 2 ]  =  9 ;  capacidades [ 1 ] [ 2 ]  =  1 ;  capacidades [ 1 ] [ 3 ]  =  0 ;  capacidades [ 1 ] [ 4 ]  =  0 ;  capacidades [ 2 ] [ 4 ]  =  7 ; capacidades [ 3 ] [ 5 ]  =  7 ;  capacidades [ 4 ] [ 5 ]  =  4 ; printf ( "Capacidad: \ n " );  printMatrix ( capacidades ); printf ( "Flujo máximo: \ n % d \ n " ,  pushRelabel ( capacidades ,  flujo ,  0 ,  5 )); printf ( "Flujos: \ n " );  printMatrix ( flujo ); return  0 ; }

Implementación de Python

def  relabel_to_front ( C ,  fuente :  int ,  sink :  int )  ->  int :  n  =  len ( C )  # C es la matriz de capacidad  F  =  [[ 0 ]  *  n  para  _  en  rango ( n )]  # capacidad residual de u av es C [u] [v] - F [u] [v] altura  =  [ 0 ]  *  n  # altura del nodo  exceso  =  [ 0 ]  *  n  # flujo en nodo menos fluir desde el nodo  visto  =  [ 0 ]  *  n  # vecinos visto desde la última reetiquetado  # nodo "cola"  lista de nodos  =  [ i  para  i  en  rango ( n )  si  i  ! =  fuente  e  i  ! =  sumidero ] def  push ( u ,  v ):  enviar  =  min ( exceso [ u ],  C [ u ] [ v ]  -  F [ u ] [ v ])  F [ u ] [ v ]  + =  enviar  F [ v ] [ u ]  - =  enviar  exceso [ u ]  - =  enviar  exceso [ v ]  + =  enviar def  relabel ( u ):  # Encuentra la nueva altura más pequeña que hace posible un empujón,  # si tal empujón es posible.  min_height  =  ∞  para  v  en  xrange ( n ):  si  C [ u ] [ v ]  -  F [ u ] [ v ]  >  0 :  min_height  =  min ( min_height ,  height [ v ])  height [ u ]  =  min_height +  1 def  descarga ( u ):  mientras que el  exceso [ u ]  >  0 :  si se  ve [ u ]  <  n :  # marque el siguiente vecino  v  =  visto [ u ]  si  C [ u ] [ v ]  -  F [ u ] [ v ]  >  0  y  altura [ u ]  >  altura [ v ]:  empujar (u ,  v )  else :  visto [ u ]  + =  1  else :  # hemos comprobado todos los vecinos. debe volver a  etiquetar volver a etiquetar ( u )  visto [ u ]  =  0 altura [ fuente ]  =  n  # la ruta más larga desde la fuente al sumidero es menor que n  exceso largo [ fuente ]  =  ∞  # enviar tanto flujo como sea posible a los vecinos de la fuente  para  v  en  rango ( n ):  empujar ( fuente ,  v ) p  =  0  , mientras que  p  <  len ( lista de nodos ):  u  =  lista de nodos [ p ]  old_height  =  altura [ u ]  de descarga ( u )  si  la altura [ u ]  >  old_height :  lista de nodos . insert ( 0 ,  nodelist . pop ( p ))  # mover al frente de la lista  p  =  0  # comenzar desde el frente de la lista  else:  p  + =  1 devolver  suma ( F [ fuente ])

Referencias

^ a b c Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). "§26 Caudal máximo". Introducción a los algoritmos (2ª ed.). La prensa del MIT. págs. 643 –698. ISBN 978-0262032933.
^ a b c d e f g Goldberg, AV; Tarjan, RE (1986). "Un nuevo enfoque al problema del caudal máximo". Actas del decimoctavo simposio anual de ACM sobre teoría de la computación - STOC '86 . pag. 136. doi : 10.1145 / 12130.12144 . ISBN 978-0897911931.
^ a b Ahuja, Ravindra K .; Kodialam, Murali; Mishra, Ajay K .; Orlin, James B. (1997). "Investigaciones computacionales de algoritmos de flujo máximo". Revista europea de investigación operativa . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi : 10.1016 / S0377-2217 (96) 00269-X .
↑ a b c Goldberg, Andrew V. (2008). "El algoritmo de aumento parcial-reetiquetado para el problema de flujo máximo". Algoritmos - ESA 2008 . Apuntes de conferencias en Ciencias de la Computación. 5193 . págs. 466–477. CiteSeerX 10.1.1.150.5103 . doi : 10.1007 / 978-3-540-87744-8_39 . ISBN 978-3-540-87743-1.
^ Goldberg, Andrew V (1997). "Una implementación eficiente de un algoritmo de flujo de costo mínimo de escala". Revista de algoritmos . 22 : 1–29. doi : 10.1006 / jagm.1995.0805 .
↑ Ahuja, Ravindra K .; Orlin, James B. (1991). "Algoritmos de trayectoria de aumento dirigidos a distancia para problemas de flujo máximo y flujo máximo paramétrico". Logística de investigación naval . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . doi : 10.1002 / 1520-6750 (199106) 38: 3 <413 :: AID-NAV3220380310> 3.0.CO; 2-J .
^ Goldberg, Andrew V .; Tarjan, Robert E. (2014). "Algoritmos eficientes de caudal máximo". Comunicaciones de la ACM . 57 (8): 82. doi : 10.1145 / 2628036 .
↑ a b c d Goldberg, Andrew V .; Tarjan, Robert E. (1988). "Un nuevo enfoque al problema del caudal máximo". Revista de la ACM . 35 (4): 921. doi : 10.1145 / 48014.61051 .
^ a b Ahuja, RK; Magnanti, TL; Orlin, JB (1993). Flujos de red: teoría, algoritmos y aplicaciones (1ª ed.). Prentice Hall. ISBN 978-0136175490.
^ Shiloach, Yossi; Vishkin, Uzi (1982). "Un algoritmo de flujo máximo paralelo O (n2log n)". Revista de algoritmos . 3 (2): 128-146. doi : 10.1016 / 0196-6774 (82) 90013-X .
^ Cheriyan, J .; Maheshwari, SN (1988). "Análisis de algoritmos push de preflujo para máximo flujo de red". Fundamentos de la tecnología del software y la informática teórica . Apuntes de conferencias en Ciencias de la Computación. 338 . pag. 30. doi : 10.1007 / 3-540-50517-2_69 . ISBN 978-3-540-50517-4.
^ Cherkassky, Boris V .; Goldberg, Andrew V. (1995). "Sobre la implementación del método push-relabel para el problema de caudal máximo". Programación de enteros y optimización combinatoria . Apuntes de conferencias en Ciencias de la Computación. 920 . pag. 157. CiteSeerX 10.1.1.150.3609 . doi : 10.1007 / 3-540-59408-6_49 . ISBN 978-3-540-59408-6.
^ Derigs, U .; Meier, W. (1989). "¿Implementación del algoritmo de flujo máximo de Goldberg? Una investigación computacional". ZOR Zeitschrift für Métodos de investigación de operaciones y modelos de investigación de operaciones . 33 (6): 383. doi : 10.1007 / BF01415937 .

[clrs26-1] Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). "§26 Caudal máximo". Introducción a los algoritmos (2ª ed.). La prensa del MIT. págs. 643 –698. ISBN 978-0262032933.

[goldberg86-2] Goldberg, AV; Tarjan, RE (1986). "Un nuevo enfoque al problema del caudal máximo". Actas del decimoctavo simposio anual de ACM sobre teoría de la computación - STOC '86 . pag. 136. doi : 10.1145 / 12130.12144 . ISBN 978-0897911931.

[ahuja97-3] Ahuja, Ravindra K .; Kodialam, Murali; Mishra, Ajay K .; Orlin, James B. (1997). "Investigaciones computacionales de algoritmos de flujo máximo". Revista europea de investigación operativa . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi : 10.1016 / S0377-2217 (96) 00269-X .

[goldberg08-4] Goldberg, Andrew V. (2008). "El algoritmo de aumento parcial-reetiquetado para el problema de flujo máximo". Algoritmos - ESA 2008 . Apuntes de conferencias en Ciencias de la Computación. 5193 . págs. 466–477. CiteSeerX 10.1.1.150.5103 . doi : 10.1007 / 978-3-540-87744-8_39 . ISBN 978-3-540-87743-1.

[goldberg97-5] Goldberg, Andrew V (1997). "Una implementación eficiente de un algoritmo de flujo de costo mínimo de escala". Revista de algoritmos . 22 : 1–29. doi : 10.1006 / jagm.1995.0805 .

[ahuja91-6] Ahuja, Ravindra K .; Orlin, James B. (1991). "Algoritmos de trayectoria de aumento dirigidos a distancia para problemas de flujo máximo y flujo máximo paramétrico". Logística de investigación naval . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . doi : 10.1002 / 1520-6750 (199106) 38: 3 <413 :: AID-NAV3220380310> 3.0.CO; 2-J .

[goldberg2014-7] Goldberg, Andrew V .; Tarjan, Robert E. (2014). "Algoritmos eficientes de caudal máximo". Comunicaciones de la ACM . 57 (8): 82. doi : 10.1145 / 2628036 .

[goldberg88-8] Goldberg, Andrew V .; Tarjan, Robert E. (1988). "Un nuevo enfoque al problema del caudal máximo". Revista de la ACM . 35 (4): 921. doi : 10.1145 / 48014.61051 .

[amo93-9] Ahuja, RK; Magnanti, TL; Orlin, JB (1993). Flujos de red: teoría, algoritmos y aplicaciones (1ª ed.). Prentice Hall. ISBN 978-0136175490.

[sv82-10] Shiloach, Yossi; Vishkin, Uzi (1982). "Un algoritmo de flujo máximo paralelo O (n2log n)". Revista de algoritmos . 3 (2): 128-146. doi : 10.1016 / 0196-6774 (82) 90013-X .

[cheriyan88-11] Cheriyan, J .; Maheshwari, SN (1988). "Análisis de algoritmos push de preflujo para máximo flujo de red". Fundamentos de la tecnología del software y la informática teórica . Apuntes de conferencias en Ciencias de la Computación. 338 . pag. 30. doi : 10.1007 / 3-540-50517-2_69 . ISBN 978-3-540-50517-4.

[cherkassky95-12] Cherkassky, Boris V .; Goldberg, Andrew V. (1995). "Sobre la implementación del método push-relabel para el problema de caudal máximo". Programación de enteros y optimización combinatoria . Apuntes de conferencias en Ciencias de la Computación. 920 . pag. 157. CiteSeerX 10.1.1.150.3609 . doi : 10.1007 / 3-540-59408-6_49 . ISBN 978-3-540-59408-6.

[derigs89-13] Derigs, U .; Meier, W. (1989). "¿Implementación del algoritmo de flujo máximo de Goldberg? Una investigación computacional". ZOR Zeitschrift für Métodos de investigación de operaciones y modelos de investigación de operaciones . 33 (6): 383. doi : 10.1007 / BF01415937 .

[1]