Algoritmo de flujo máximo de reetiquetado y empuje

En optimización matemática , el algoritmo push-relabel (o algoritmo preflow-push ) es un algoritmo para calcular flujos máximos en una red de flujo . El nombre "push-relabel" proviene de las dos operaciones básicas que utiliza. Durante su ejecución, el algoritmo mantiene un "preflow" y lo convierte gradualmente en un flujo máximo moviendo el flujo localmente entre nodos vecinos mediante operaciones push, bajo la guía de una red admisible mantenida por operaciones relabel . En comparación, el algoritmo Ford-Fulkerson realiza aumentos globales que envían el flujo siguiendo rutas desde el origen hasta el destino. ^{[ 1 ]}

El algoritmo push-relabel se considera uno de los algoritmos de flujo máximo más eficientes. El algoritmo genérico tiene una $complejidad$ temporal fuertemente polinómica $O (V²E), que es asintóticamente más eficiente que el$ algoritmo Edmonds-Karp $O (VE²)$ . ^[ $2$ ^]^Las variantes específicas de los algoritmos alcanzan complejidades temporales aún menores. La variante basada en la regla de selección del nodo de etiqueta más alta tiene $una$ $complejidad$ $temporal$ $O$ $($ $V²\sqrtE$ $)$ y generalmente se considera el punto de referencia para los algoritmos de flujo máximo. ^[³^]^[⁴^] Se puede alcanzar una complejidad temporal subcúbica $O$ $($ $VE$ $log($ $V²$ $/$ $E$ $)$ $) utilizando$ árboles dinámicos , ^[²^] aunque en la práctica es menos eficiente.

El algoritmo push-relabel se ha extendido para calcular flujos de costo mínimo . ^{[ 5 ]} La idea de las etiquetas de distancia ha dado lugar a un algoritmo de ruta de aumento más eficiente, que a su vez puede incorporarse de nuevo al algoritmo push-relabel para crear una variante con un rendimiento empírico aún mayor. ^{[ 4 ]}^{[ 6 ]}

Historia

Un preflujo es un flujo en el que la cantidad total que entra en un vértice puede ser mayor que la cantidad total que sale de él, lo que permite que un algoritmo cambie el flujo en un solo arco. ^{[ 7 ]} Esta idea fue concebida originalmente por Alexander V. Karzanov y publicada en 1974 en Soviet Mathematical Dokladi 15. Este algoritmo de preflujo también utilizaba una operación de empuje; sin embargo, utilizaba distancias en la red auxiliar para determinar dónde empujar el flujo en lugar de un sistema de etiquetado. ^{[ 2 ]}^{[ 8 ]}

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 la 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 (V2E)$ junto con una implementación $secuencial$ $O ($ $V3$ $)$ , una implementación $O (VE log( V2/ E)) usando$ árboles dinámicos y una implementación paralela/distribuida. $[$ ^{2 ] [}^{7 ] Como} se explica en, ^{[ 9 ]} Goldberg-Tarjan introdujeron etiquetas de distancia incorporándolas al 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$ (con s ≠ t) son vértices de origen y destino elegidos
$f : V \times V \to ℝ$ denota un preflujo en $F$ ,
$x f : V \to ℝ$ denota la función de exceso con respecto al flujo $f$ , definida por $x f (u) = Σ v \in V f (v, u) - Σ 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$ , definida por $c f (e) = c (e) - f (e)$ ,
$E f \subset E$ siendo las aristas donde $f < c$ ,

y

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

El algoritmo de empuje-reetiquetado utiliza una función de etiquetado válida de enteros no negativos que emplea 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 satisfacer 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 origen :

𝓁(s) = | V |

Conservación del fregadero :

𝓁(t) = 0

En el algoritmo, los valores de las etiquetas $s$ y $t$ son fijos. $𝓁(u)$ es una cota 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 una cota inferior de la distancia no ponderada de $u$ a $s$ . Como resultado, si existe una función de etiquetado válida, no hay caminos $s - t en$ $G f$ porque ningún camino de este tipo puede ser más largo que $| V | - 1$ .

Un arco $(u, v) \in E f$ se denomina 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.

Para un flujo fijo $f$ , un vértice $v \notin {s, t}$ se llama activo si tiene un exceso positivo con respecto a $f$ , es decir, $x f (u) > 0$ .

Operaciones

Inicialización

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

Empujar

La operación de empuje se aplica en un arco de salida 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$ .

push(u, v): afirmar que x _f [u] > 0 y 𝓁[u] == 𝓁[v] + 1 Δ = min(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 denomina empuje saturante, ya que utiliza toda la capacidad disponible del arco residual. En caso contrario, todo el exceso en el nodo se desplaza a través del arco residual. Esto se denomina empuje no saturante .

Reetiquetar

La operación de reetiquetado se aplica a un nodo activo $u$ que no es ni la fuente ni el sumidero sin ningún arco de salida admisible en $G f$ . Modifica $𝓁(u)$ para que sea el valor mínimo tal que se cree un arco de salida admisible. Nótese que esto siempre aumenta $𝓁(u)$ y nunca crea un arco pronunciado, que es un arco $(u, v)$ tal que $c f (u, v) > 0$ , y $𝓁(u) > 𝓁(v) + 1$ .

relabel(u): afirmar que 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 empuje y reetiquetado

Después de una operación de empuje o reetiquetado, $𝓁$ 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 comprobar 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 de salida de u en $G f$ . Para los arcos de entrada de $u$ en $G f$ $, el 𝓁(u)$ incrementado solo puede satisfacer las restricciones de forma menos estricta, no violarlas.

El algoritmo genérico de reetiquetado y reenvío

El algoritmo genérico de envío y reetiquetado se utiliza únicamente como prueba de concepto y no contiene detalles de implementación sobre cómo seleccionar un nodo activo para las operaciones de enví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)$ satisfaga la condición de etiquetado válido $s$ debe estar desconectado de $t$ . En la inicialización, el algoritmo cumple este requisito creando un preflujo $f$ que satura todos los arcos de salida de $s$ , después de lo cual $𝓁(v) = 0$ es trivialmente válido para todo $v ∈ V \ { s , t }$ . Después de la inicialización, el algoritmo ejecuta repetidamente una operación de empuje o reetiquetado aplicable hasta que no se apliquen tales operaciones, momento en el que el preflujo se ha convertido en un flujo máximo.

generic-push-relabel(G, c, s, t): crear un flujo previo f que sature todos los arcos de salida de s sea 𝓁[s] = |V| sea 𝓁[v] = 0 para todo v ∈ V \ {s} mientras haya una operación de empuje 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 demostrar examinando los efectos de las operaciones de empuje y reetiquetado en la función de etiqueta $𝓁$ . La operación de reetiquetado aumenta el valor de la etiqueta en el mínimo asociado más uno, lo 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álido $𝓁(u) \leq 𝓁(v) + 1$ solo se aplica a los arcos residuales en $G f$ . ^{[ 7 ]}

Si existe un preflujo $f$ y un etiquetado válido $𝓁$ para $f,$ entonces no hay camino de aumento de $s$ a $t$ en el grafo residual $G f$ . Esto se puede demostrar por contradicción basándose 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 $los v ∈ V \ { s , t }$ no tienen flujo excedente, y sin exceso el preflujo $f$ obedece la restricción de conservación del flujo y puede considerarse un flujo normal. Este flujo es el flujo máximo según el teorema del corte mínimo de flujo máximo ya que no hay camino de aumento de $s$ a $t$ . ^{[ 7 ]}

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

complejidad temporal

Para acotar la complejidad temporal del algoritmo, debemos analizar el número de operaciones de inserción y reetiquetado que se producen dentro del bucle principal. El número de operaciones de reetiquetado, inserción saturada e inserción no saturada se analiza 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 máximo de etiqueta es como máximo $2| V | - 1$ para todos los nodos. Esto significa que la operación de reetiquetado podría realizarse potencialmente $2| V | - 1$ veces para todos los nodos $V \ { s , t }$ (es decir $, | V | - 2$ ). Esto resulta en una cota 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 que el arco se reinserte en $G f$ para otro empuje de saturación, primero se debe volver a etiquetar $v , seguido de un empuje en el arco$ $(v, u)$ , luego se debe volver a etiquetar $u$ . En el proceso, $𝓁(u)$ aumenta en al menos dos. Por lo tanto, hay $O (V)$ empujes de saturación en $(u, v)$ , y el número total de empujes de saturación es como máximo $2| V || E |$ . Esto resulta en un límite de tiempo de $O (VE)$ para las operaciones de empuje de saturación.

La limitación del número de empujes no saturantes se puede lograr mediante un argumento potencial . Usamos la función potencial $Φ = Σ [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 toda la ejecución del algoritmo. Tanto los reetiquetados como los empujes saturantes pueden aumentar $Φ$ . Sin embargo, el valor de $Φ$ debe ser igual a 0 al finalizar, ya que no puede haber nodos activos restantes al final de la ejecución del algoritmo. Esto significa que, durante la ejecución del algoritmo, los empujes no saturantes deben compensar la diferencia de las operaciones de reetiquetado y empuje saturante para que $Φ$ termine con un valor de 0. La operación de reetiquetado puede aumentar $Φ$ en como máximo $(2| V | - 1)(| V | - 2)$ . Un empuje saturante en $(u, v)$ activa $v$ si estaba inactivo antes del empuje, aumentando $Φ$ en como máximo $2| V | - 1.$ Por lo tanto, la contribución total de todas las operaciones de empuje saturantes a $Φ$ es como máximo $(2| V | - 1)(2| V || E |)$ . Un empuje no saturante en $(u, v)$ siempre desactiva $u$ , pero también puede activar $v$ como en un empuje saturante. Como resultado, disminuye $Φ$ en al menos $𝓁(u) - 𝓁(v) = 1$ . Dado que los reetiquetados y los empujes de saturación aumentan $Φ$ , el número total de empujes no saturantes debe compensar la diferencia de $(2| V | - 1)(| V | - 2) + (2| V | - 1)(2| V || E |) \leq 4| V | 2 | E |$ . Esto resulta en un límite de tiempo de $O (V 2 E)$ para las operaciones de empuje no saturantes.

En resumen, el algoritmo ejecuta $O (V²)$ reetiquetados, $O (VE$ $)$ inserciones saturantes y $O (V²E) inserciones no saturantes. Las estructuras$ ^de datos pueden diseñarse para seleccionar y ejecutar una operación aplicable en $tiempo$ $O (1) . Por$ $lo$ tanto, la complejidad temporal del algoritmo es $O (V²E)$ . ^{[ 1 ]}^[ $7$ ^]

Ejemplo

A continuación se muestra un ejemplo de ejecución del algoritmo genérico de reetiquetado y envío, tal como se definió anteriormente, en el siguiente diagrama de flujo de red simple.

Grafo de red de flujo inicial

Gráfico de red de flujo máximo final

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

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

Implementaciones prácticas

Si bien el algoritmo genérico de inserción y reetiquetado tiene una complejidad temporal $de O (V²E),$ las implementaciones eficientes alcanzan una complejidad temporal $de$ $O (V³) o inferior al aplicar reglas apropiadas para seleccionar las$ operaciones de inserción y reetiquetado aplicables. El rendimiento empírico puede mejorarse aún más mediante heurísticas.

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

La estructura de datos "arco actual" es un mecanismo para visitar los vecinos entrantes y salientes de un nodo en la red de flujo en un orden circular estático. Si se crea una lista enlazada simple de vecinos para un nodo, la estructura de datos puede ser tan simple como un puntero a la lista que la recorre y regresa al inicio cuando llega al final.

A partir de la estructura de datos "arco de corriente", se puede definir la operación de descarga. Esta operación se aplica a un nodo activo y empuja repetidamente el flujo desde el nodo hasta que se vuelve inactivo, reetiquetándolo según sea necesario para crear arcos admisibles durante el proceso.

descarga(u): mientras x _f [u] > 0 hacer si current-arc[u] ha salido del final de neighbors[u] entonces reetiquetar(u) rebobinar arco de corriente[u] de lo contrario sea (u, v) = current-arc[u] si (u, v) es admisible entonces empujar(u, v) Dejemos que current-arc[u] apunte al siguiente vecino de u.

Encontrar el siguiente margen admisible para seguir adelante ha sido $O(1)$ complejidad amortizada . El puntero del arco actual solo se mueve al siguiente vecino cuando la arista al vecino actual está saturada o no es admisible, y ninguna de estas dos propiedades puede cambiar hasta que el nodo activo $u$ se vuelve a etiquetar. Por lo tanto, cuando el puntero se agota, no hay aristas insaturadas admisibles y tenemos que volver a etiquetar el nodo activo. $u$ , habiendo movido el puntero $O(V)$ veces es pagado por el $O(V)$ operación de reetiquetado. ^{[ 7 ]}

Reglas de selección de nodos activos

La definición de la operación de descarga reduce el algoritmo de reetiquetado a la selección repetida de un nodo activo para su descarga. Dependiendo de la regla de selección, el algoritmo presenta diferentes complejidades temporales. Para simplificar, en la siguiente discusión, omitiremos $s$ y $t$ al referirnos a los nodos.

Regla de selección FIFO

El algoritmo FIFO push-relabel ^{[ 2 ]} organiza los nodos activos en una cola. Los nodos activos iniciales pueden insertarse en cualquier orden. El algoritmo siempre elimina el nodo que se encuentra al principio de la cola para su descarga. Cuando un nodo inactivo se activa, se añade al final de la cola.

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

Regla de selección de reetiquetado al frente

El algoritmo de reetiquetado y reetiquetado ^{[ 1 ]} organiza todos los nodos en una lista enlazada y mantiene la invariante de que la lista está ordenada topológicamente con respecto a la red admisible. El algoritmo recorre 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 reetiqueta, se mueve al principio de la lista y el recorrido se reinicia desde el principio.

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

Regla de selección de etiqueta más alta

El algoritmo push-relabel de etiqueta más alta ^{[ 11 ]} organiza todos los nodos en cubetas indexadas por sus etiquetas. El algoritmo siempre selecciona un nodo activo con la etiqueta más alta para descargarlo.

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

Técnicas de implementación

Aunque en la descripción del algoritmo genérico de empuje-reetiquetado anterior, $𝓁(u)$ se establece en cero para cada nodo u distinto de $s$ y $t$ al principio, es preferible realizar una búsqueda en anchura hacia atrás desde $t$ para calcular las etiquetas exactas. ^{[ 2 ]}

El algoritmo se divide típicamente en dos fases. La primera fase calcula un flujo previo máximo descargando solo los nodos activos cuyas etiquetas son inferiores a $n$ . La segunda fase convierte el flujo previo máximo en un flujo máximo devolviendo a $s el flujo excedente que no puede alcanzar$ $t$ . Se puede demostrar que la segunda fase tiene una complejidad temporal de $O$ $($ $VE$ $)$ independientemente del orden de las operaciones de inserción y reetiquetado, y por lo tanto está dominada por la primera fase. Alternativamente, se puede implementar utilizando la descomposición del flujo. ^[⁹^]

Las heurísticas son cruciales para mejorar el rendimiento empírico del algoritmo. ^{[ 12 ]} Dos heurísticas comúnmente utilizadas son la heurística de brecha y la heurística de reetiquetado global. ^{[ 2 ]}^{[ 13 ]} La heurística de brecha detecta brechas en la función de etiquetado. Si hay una etiqueta 0 < 𝓁 ' < | V | para la cual no hay ningún nodo $u$ tal que $𝓁(u) = 𝓁'$ , entonces cualquier nodo $u$ con $𝓁' < 𝓁(u) < | V |$ se ha desconectado de $t$ y puede ser reetiquetado a $(| V | + 1)$ inmediatamente. La heurística de reetiquetado global realiza periódicamente una búsqueda en anchura hacia atrás 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 ]}

Ejemplos de implementación

Implementación en C

#include <stdlib.h> #include <stdio.h>#define NODES 6 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) #define INFINITE 10000000void 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 ; for ( v = 0 ; v < NODES ; v ++ ) { if ( C [ u ][ v ] - F [ u ][ v ] > 0 ) { min_height = MIN ( min_height , height [ v ]); height [ u ] = min_height + 1 ; } } };void discharge ( const int * const * C , int ** F , int * excess , int * height , int * seen , int u ) { while ( excess [ u ] > 0 ) { if ( seen [ u ] < NODES ) { int v = seen [ u ]; if (( C [ u ][ v ] - F [ u ][ v ] > 0 ) && ( height [ u ] > height [ v ])) { push ( C , F , excess , u , v ); } else { seen [ u ] += 1 ; } } else { relabel ( C , F , height , u ); seen [ u ] = 0 ; } } }void moveToFront ( int i , int * A ) { int temp = A [ i ]; int n ; for ( n = i ; n > 0 ; n -- ) { A [ n ] = A [ n -1 ]; } A [ 0 ] = temp ; }int pushRelabel ( const int * const * C , int ** F , int source , int sink ) { int * excess , * height , * list , * seen , i , p ;exceso = ( int * ) calloc ( NODOS , sizeof ( int )); altura = ( int * ) calloc ( NODOS , sizeof ( int )); visto = ( int * ) calloc ( NODOS , sizeof ( int ));lista = ( int * ) calloc (( NODES -2 ), sizeof ( int ));for ( i = 0 , p = 0 ; i < NODES ; i ++ ){ if (( i != source ) && ( i != sink )) { list [ p ] = i ; p ++ ; } }altura [ origen ] = NODOS ; exceso [ origen ] = INFINITO ; para ( i = 0 ; i < NODOS ; i ++ ) empujar ( C , F , exceso , origen , i );p = 0 ; mientras ( p < NODES - 2 ) { int u = lista [ p ]; int old_height = altura [ u ]; descarga ( C , F , exceso , altura , visto , u ); si ( altura [ u ] > old_height ) { moverAlFrente ( p , lista ); p = 0 ; } else { p += 1 ; } } int flujoMáximo = 0 ; para ( i = 0 ; i < NODES ; i ++ ) flujoMáximo += F [ fuente ][ i ];gratis ( lista );libre ( visto ); libre ( altura ); libre ( exceso );devolver flujo máximo ; }void printMatrix ( const int * const * M ) { int i , j ; for ( i = 0 ; i < NODES ; i ++ ) { for ( j = 0 ; j < NODES ; j ++ ) printf ( "%d \t " , M [ i ][ j ]); printf ( " \n " ); } }int main ( void ) { int ** flujo , ** capacidades , i ; flujo = ( int ** ) calloc ( NODOS , sizeof ( int * )); capacidades = ( int ** ) calloc ( NODOS , sizeof ( int * )); for ( i = 0 ; i < NODOS ; i ++ ) { flujo [ i ] = ( int * ) calloc ( NODOS , sizeof ( int )); capacidades [ i ] = ( int * ) calloc ( NODOS , sizeof ( int )); }// Gráfico de muestra capacidades [ 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 ( flow );devolver 0 ; }

Implementación en Python

def relabel_to_front ( C , source : int , sink : int ) -> int : """Algoritmo de flujo máximo de empuje-reetiquetado.""" n = len ( C ) # C es la matriz de capacidad F = [[ 0 ] * n for _ in range ( n )] # la capacidad residual de u a v es C[u][v] - F[u][v]altura = [ 0 ] * n # altura del nodo exceso = [ 0 ] * n # flujo hacia el nodo menos flujo desde el nodo visto = [ 0 ] * n # vecinos vistos desde el último reetiquetado # nodo "cola" lista de nodos = [ i para i en rango ( n ) si i != origen y i != sumidero ]def push ( u , v ): send = min ( exceso [ u ], C [ u ][ v ] - F [ u ][ v ]) F [ u ][ v ] += send F [ v ][ u ] -= send exceso [ u ] -= send exceso [ v ] += senddef relabel ( u ): # Encuentra la altura nueva más pequeña que haga posible un empuje, # si es que tal empuje es posible. min_height = ∞ for v in range ( n ): if C [ u ][ v ] - F [ u ][ v ] > 0 : min_height = min ( min_height , height [ v ]) height [ u ] = min_height + 1def descarga ( u ): mientras exceso [ u ] > 0 : si visto [ u ] < n : # comprobar el siguiente vecino v = visto [ u ] si C [ u ][ v ] - F [ u ][ v ] > 0 y altura [ u ] > altura [ v ]: empujar ( u , v ) de lo contrario : visto [ u ] += 1 de lo contrario : # hemos comprobado todos los vecinos. debemos volver a etiquetar volver a etiquetar ( u ) visto [ u ] = 0altura [ origen ] = n # el camino más largo desde el origen hasta el sumidero es menor que n de longitud exceso [ origen ] = ∞ # enviar tanto flujo como sea posible a los vecinos del origen para v en rango ( n ): empujar ( origen , v )p = 0 mientras p < len ( lista de nodos ): u = lista de nodos [ p ] old_height = altura [ u ] discharge ( u ) si altura [ u ] > old_height : lista de nodos . insert ( 0 , lista de nodos . pop ( p )) # mover al principio de la lista p = 0 # empezar desde el principio de la lista else : p += 1devolver suma ( F [ origen ])

Implementación base de R

# (HL) Algoritmo de flujo máximo de reetiquetado por empuje. # Regla de selección de nodo activo: etiqueta más alta. # R {base}.push <- function ( u , v ) { d <- min ( excess [ u ], rGraph [ u , v ]) rGraph [ u , v ] <<- rGraph [ u , v ] - d # Arista hacia adelante, sin flujo. rGraph [ v , u ] <<- rGraph [ v , u ] + d # Arista hacia atrás, flujo enrutado previamente, excess [ u ] <<- excess [ u ] - d # que se puede deshacer. excess [ v ] <<- excess [ v ] + d pushCtr <<- pushCtr + 1L stopifnot ( pushCtr <= nV ^ 2 * sqrt ( nE )) }relabel <- function ( u ) { height [ u ] <<- height [ u ] + 1L relabCtr <<- relabCtr + 1L }# Descarga el vértice u ≠ {s, t} a través del grafo de red residual. # Una arista (u, v) se llama admisible si height[u] == height[v] + 1. discharge <- function ( u ) { neighbors <- which ( rGraph [ u , ] > 0 ) admisible <- neighbors [ which ( height [ u ] == height [ neighbors ] + 1L )] for ( v in admisible ) { push ( u , v ) if ( excess [ u ] == 0 ) break } if ( excess [ u ] > 0 ) relabel ( u ) }# Preflujo: flujo con restricciones de conservación relajadas: flujo de entrada ≥ flujo de salida. # Mover el flujo excedente sobre los bordes admisibles hacia el sumidero. # Datos globales eCap, rGraph, exceso, altura. Indexado por id de vértice basado en 1. pushRelabel <- function ( source , sink ) { rGraph <<- eCap # Grafo de red residual. exceso <<- # Flujo de entrada menos flujo de salida (≥ 0). altura <<- rep ( 0L , nV ) # Valor de la etiqueta (𝓁).altura [ origen ] <<- nV exceso [ origen ] <<- Inf relabCtr <<- pushCtr <<- 0L # Contar reetiquetar, empujar.# Empujar el exceso desde la fuente. sourceOut <- which ( rGraph [ source , ] > 0 ) for ( i in sourceOut ) push ( source , i )# Bucle principal. Seleccionar la etiqueta más alta con exceso positivo, # de todos los nodos excepto la fuente y el sumidero, luego descargar. nlist <- setdiff ( seq ( from = 1 , to = nV , by = 1 ), c ( source , sink )) while (( active <- nlist [ which ( excess [ nlist ] > 0 )]) |> length () > 0 ) { u <- active [ which ( height [ active ] == max ( height [ active ]))][ 1 ] discharge ( u ) } # Todo el flujo excedente se ha enviado al sumidero. return ( sum (( eCap - rGraph )[ source , ])) }# Gráfico de torneo, n = 4, flujo máximo = n - 1. eCap <- matrix ( 1L , 4 , 4 ); diag ( eCap ) <- 0L colnames ( eCap ) <- c ( "s" , seq ( 2 , length.out = ncol ( eCap ) - 2 ), "t" ) # La fuente es 1, el sumidero es n. print ( list ( "Matriz de capacidad" = eCap ), max = 1600 )# Calcula el flujo máximo entre la fuente y el sumidero. nV <- ncol ( eCap ) # Vértices. nE <- sum ( eCap > 0 ) # Aristas. system.time ( maxFlow <- pushRelabel ( source = 1L , sink = nV )) print ( paste ( "VE =" , nV , nE , "maxFlow =" , maxFlow )) print ( paste ( "Relabel =" , relabCtr , "Push =" , pushCtr ))# Comprobar que la matriz de flujo es antisimétrica. # Comprobar que el flujo que sale de la fuente (=1) es igual al flujo que entra en el sumidero (=nV). flujo <- eCap - rGraph stopifnot (((( flujo ) == - t ( flujo )) |> all ())) stopifnot ( rowSums ( flujo )[ 1 ] == colSums ( flujo )[ nV ])# Matriz de adyacencia ponderada del grafo de red de flujo máximo final. mxFlow <- pmax ( flow , 0 ) print ( list ( "Grafo de red residual" = rGraph )) print ( list ( "Flujo máximo" = mxFlow ))

Véase también

Apuntes de clase de Tim Roughgarden , Un segundo curso de algoritmos (CS261, invierno de 2016) , Universidad de Columbia, Nueva York.

Referencias

1 2 3 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.
1 2 3 4 5 6 7 Goldberg, AV; Tarjan, RE (1986). "Un nuevo enfoque al problema del flujo máximo". Actas del decimoctavo simposio anual de la ACM sobre Teoría de la Computación – STOC '86 . pág. 136. doi : 10.1145/12130.12144 . ISBN 978-0897911931. S2CID 14492800 .
1 2 Ahuja, Ravindra K.; Kodialam, Murali; Mishra, Ajay K.; Orlin, James B. (1997). "Investigaciones computacionales de algoritmos de flujo máximo". European Journal of Operational Research . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi : 10.1016/S0377-2217(96)00269-X .
1 2 3 Goldberg, Andrew V. (2008). "El algoritmo de aumento parcial y reetiquetado para el problema del flujo máximo". Algoritmos – ESA 2008. Notas de clase en ciencias de la computación. Vol. 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 escalable". Journal of Algorithms . 22 : 1–29 . doi : 10.1006/jagm.1995.0805 .
↑ Ahuja, Ravindra K.; Orlin, James B. (1991). "Algoritmos de ruta de aumento dirigidos por distancia para problemas de flujo máximo y flujo máximo paramétrico". Naval Research Logistics . 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 .
1 2 3 4 5 6 Goldberg, Andrew V.; Tarjan, Robert E. (1988). "Un nuevo enfoque al problema del flujo máximo" . Journal of the ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID 52152408 .
↑ Goldberg, Andrew V.; Tarjan, Robert E. (2014). "Algoritmos eficientes de flujo máximo". Communications of the ACM . 57 (8): 82. doi : 10.1145/2628036 . S2CID 17014879 .
1 2 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)". Journal of Algorithms . 3 (2): 128– 146. doi : 10.1016/0196-6774(82)90013-X .
↑ Cheriyan, J.; Maheshwari, SN (1988). "Análisis de algoritmos de empuje de preflujo para flujo máximo de red". Fundamentos de la tecnología del software y la informática teórica . Notas de clase en informática. Vol. 338. p. 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 del flujo máximo". Programación entera y optimización combinatoria . Notas de clase en ciencias de la computación. Vol. 920. pág. 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). "¿Implementar el algoritmo de flujo máximo de Goldberg ? Una investigación computacional". Zeitschrift für Investigación de operaciones . 33 (6): 383. doi : 10.1007/BF01415937 . S2CID 39730584 .

[clrs26-1] 1 2 3 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] 1 2 3 4 5 6 7 Goldberg, AV; Tarjan, RE (1986). "Un nuevo enfoque al problema del flujo máximo". Actas del decimoctavo simposio anual de la ACM sobre Teoría de la Computación – STOC '86 . pág. 136. doi : 10.1145/12130.12144 . ISBN 978-0897911931. S2CID 14492800 .

[ahuja97-3] 1 2 Ahuja, Ravindra K.; Kodialam, Murali; Mishra, Ajay K.; Orlin, James B. (1997). "Investigaciones computacionales de algoritmos de flujo máximo". European Journal of Operational Research . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi : 10.1016/S0377-2217(96)00269-X .

[goldberg08-4] 1 2 3 Goldberg, Andrew V. (2008). "El algoritmo de aumento parcial y reetiquetado para el problema del flujo máximo". Algoritmos – ESA 2008. Notas de clase en ciencias de la computación. Vol. 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 escalable". Journal of Algorithms . 22 : 1–29 . doi : 10.1006/jagm.1995.0805 .

[ahuja91-6] Ahuja, Ravindra K.; Orlin, James B. (1991). "Algoritmos de ruta de aumento dirigidos por distancia para problemas de flujo máximo y flujo máximo paramétrico". Naval Research Logistics . 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 .

[goldberg88-7] 1 2 3 4 5 6 Goldberg, Andrew V.; Tarjan, Robert E. (1988). "Un nuevo enfoque al problema del flujo máximo" . Journal of the ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID 52152408 .

[goldberg2014-8] Goldberg, Andrew V.; Tarjan, Robert E. (2014). "Algoritmos eficientes de flujo máximo". Communications of the ACM . 57 (8): 82. doi : 10.1145/2628036 . S2CID 17014879 .

[amo93-9] 1 2 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)". Journal of Algorithms . 3 (2): 128– 146. doi : 10.1016/0196-6774(82)90013-X .

[cheriyan88-11] Cheriyan, J.; Maheshwari, SN (1988). "Análisis de algoritmos de empuje de preflujo para flujo máximo de red". Fundamentos de la tecnología del software y la informática teórica . Notas de clase en informática. Vol. 338. p. 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 del flujo máximo". Programación entera y optimización combinatoria . Notas de clase en ciencias de la computación. Vol. 920. pág. 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). "¿Implementar el algoritmo de flujo máximo de Goldberg ? Una investigación computacional". Zeitschrift für Investigación de operaciones . 33 (6): 383. doi : 10.1007/BF01415937 . S2CID 39730584 .

[ 1 ]

[

[

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]