Algoritmo de Dinit

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 24 de mayo de 2021; las comprobaciones requieren 3 ediciones .

El algoritmo de Dinitz es un algoritmo polinomial para encontrar el flujo máximo en una red de transporte , propuesto en 1970 por el matemático soviético (más tarde israelí) Efim Dinitz . La complejidad temporal del algoritmo es . Tal estimación se puede obtener introduciendo los conceptos de una red auxiliar y un flujo de bloqueo (pseudo-máximo) . En redes con anchos de banda unitarios, existe una estimación de complejidad temporal más fuerte: . $O(|V|^{2}|E|)$ ${\ estilo de visualización O (| E || V |)}$

Descripción

Sea una red de transporte , en la que y son, respectivamente, el rendimiento y el flujo a través del borde . $G=(V,E,c,s,t)$ $c(u,v)$ $f(u,v)$ $(u,v)$

El ancho de banda residual es un mapeo definido como:

{\displaystyle c_{f}\colon V\times V\to \mathbb {R} ^{+))

si , ${\ estilo de visualización (u, v) \ en E}$ $c_{f}(u,v)=c(u,v)-f(u,v)$ ${\ Displaystyle c_ {f} (v, u) = f (u, v)}$ En otras fuentes $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$
${\ estilo de visualización c_ {f} (u, v) = 0}$ de lo contrario.

Gráfico de red residual , donde

G_{f}=(V,E_{f},c_{f}|_{E_{f)),s,t)

{\displaystyle E_{f}=\{(u,v)\in V\times V\mid c_{f}(u,v)>0\))

. Un camino complementario es un camino en el gráfico residual .

{\ Displaystyle st}

G_f

Sea la longitud del camino más corto de a en el gráfico . Entonces la red auxiliar del grafo es el grafo , donde

\operatorname {dist} (v)

s

v

G_f

G_f

G_{L}=(V,E_{L},c_{f}|_{E_{L)),s,t)

{\displaystyle E_{L}=\{(u,v)\in E_{f}\mid \operatorname {dist} (v)=\operatorname {dist} (u)+1\))

. Un flujo de bloqueo es un flujo tal que el gráfico c no contiene una ruta.

{\ Displaystyle st}

F

G'=(V,E_{L}',c_{f}|_{E_{L)),s,t)

E_{L}'=\{(u,v)\mid f(u,v)<c_{f}|_{E_{L}}(u,v)\}

{\ Displaystyle st}

Algoritmo

algoritmo de Dinit

Entrada : Red .

G=(V,E,c,s,t)

Salida : caudal máximo .

{\ Displaystyle st}

F

Instalar para cada uno . ${\ estilo de visualización f (e) = 0}$ $e\en E$
Crear a partir de un gráfico . Si , detener y dar salida . $G_L$ $G_f$ $GRAMO$ $\operatorname {dist} (t)=\infty$ $F$
Encuentra un hilo de bloqueo en . $F'$ $G_L$
Aumente flujo con flujo y vaya al paso 2. $F$ $F'$

Análisis

Se puede demostrar que cada vez que el número de aristas en el camino más corto desde la fuente hasta el sumidero aumenta en al menos uno, por lo que no hay más flujos de bloqueo en el algoritmo, donde está el número de vértices en la red. La red auxiliar se puede construir mediante el recorrido transversal en el tiempo , y el flujo de bloqueo en cada nivel del gráfico se puede encontrar en el tiempo . Por lo tanto, el tiempo de ejecución del algoritmo Dinits es . $n-1$ $norte$ $G_L$ $O(|V|+|E|)$ ${\ estilo de visualización O (| V || E |)}$ $O(|V|)\cdot (O(|V|+|E|)+O(|V||E|))=O(|V|^{2}|E|)$

Usando estructuras de datos llamadas árboles dinámicos , es posible encontrar el flujo de bloqueo en cada fase en el tiempo , luego el tiempo de ejecución del algoritmo de Dinitz se puede mejorar a . $O(|E|\log |V|)$ $O(|V||E|\log |V|)$

Ejemplo

A continuación se muestra una simulación del algoritmo de Dinitz. En la red auxiliar, los vértices con etiquetas rojas son los valores . El hilo de bloqueo está marcado en azul. $G_L$ $\operatorname {dist} (v)$

	$GRAMO$	$G_f$	$G_L$
una.
	Un hilo de bloqueo consta de rutas: ${\ estilo de visualización \ {s, 1,3, t \}}$ con 4 unidades de flujo, ${\ estilo de visualización \ {s, 1,4, t \}}$ con 6 unidades de flujo, y ${\ estilo de visualización \ {s, 2,4, t \}}$ con 4 unidades de flujo. Por lo tanto, el flujo de bloqueo contiene 14 unidades y el valor del flujo es 14. Tenga en cuenta que el camino complementario tiene 3 aristas. $\|f\|$
2.
	Un hilo de bloqueo consta de rutas: ${\ estilo de visualización \ {s, 2, 4, 3, t \}}$ con 5 unidades de flujo. Por lo tanto, el flujo de bloqueo contiene 5 unidades y el valor del flujo es 14 + 5 = 19. Tenga en cuenta que el camino complementario tiene 4 aristas. $\|f\|$
3.
	El stock no es accesible en la red . Por lo tanto, el algoritmo se detiene y devuelve el flujo máximo de magnitud 19. Tenga en cuenta que en cada flujo de bloqueo, el número de aristas en la ruta complementaria se incrementa en al menos uno. $t$ $G_f$

Historia

El algoritmo de Dinitz fue publicado en 1970 por el excientífico soviético Efim Dinitz, ahora miembro de la Facultad de Ingeniería Informática de la Universidad Ben-Gurion (Israel), anterior al algoritmo de Edmonds-Karp , que fue publicado en 1972, pero creado anteriormente. Demostraron de forma independiente que en el algoritmo de Ford-Fulkerson , si el camino complementario es el más corto, la longitud del camino complementario no disminuye.

Algoritmo de Dinitz con propagación

La complejidad del tiempo del algoritmo se puede reducir optimizando el proceso de encontrar un hilo de bloqueo. Para ello, es necesario introducir el concepto de potencial . El potencial de borde es , y el potencial de vértice es . Por la misma lógica , a . La idea de la mejora es buscar un vértice con el mínimo potencial positivo en la red auxiliar y construir un flujo de bloqueo a través de él usando colas . ${\ estilo de visualización e \ en E}$ $\operatorname {olla} (e)=c_{f}(e)$ $v\in V\setminus \{s,t\}$ $\operatorname {pot} (v)=\min\{\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e),\sum _{e\in \ delta ^{-}(v)}\nombre del operador {pot} (e)\}$ $\operatorname {pote} (s)=\sum _{e\in \delta ^{+}(v)}\operatorname {pote} (e)$ $\operatorname {pot} (t)=\sum _{e\in \delta ^{-}(v)}\operatorname {pot} (e)$

Entrada : Red .

G=(V,E,c,s,t)

Salida : caudal máximo .

{\ Displaystyle st}

F

Instalar para cada uno . ${\ estilo de visualización f (e) = 0}$ $e\en E$
Crear a partir de un gráfico . Si , detener y dar salida . $G_L$ $G_f$ $GRAMO$ $\operatorname {dist} (s,t)=\infty$ $F$
Instalar para cada uno . ${\ estilo de visualización f' (e) = 0}$ $e\en E$
Determine el potencial de cada vértice.
Siempre que exista un vértice tal que : $v\en V$ $\operatorname {bote} (v)>0$
1. Defina el flujo utilizando la propagación directa desde . $F''$ $v$
2. Determine el flujo utilizando la retropropagación desde . ${\ estilo de visualización f''}$ $v$
3. Complete la secuencia con secuencias y . $F'$ $F''$ ${\ estilo de visualización f''}$
Aumente flujo con flujo y vaya al paso 2. $F$ $F'$

Los algoritmos de propagación hacia adelante y hacia atrás sirven para encontrar caminos de a y de a, respectivamente. Un ejemplo del algoritmo de propagación directa usando colas: $v$ $t$ $s$ $v$

Entrada : Red auxiliar , vértice tal que .

G_{L}=(V,E_{L},c_{f}|_{E_{L)),s,t)

v\en V

\operatorname {bote} (v)>0

Salida : un flujo desde el origen hasta el vértice que forma parte de un flujo de bloqueo.

F''

s

v

Instalar para todos : . $w\in V\setminus \{v\}$ ${\ estilo de visualización U (w) = 0}$
Instalar y . $U(v)=\operatorname {olla} (v)$ $\operatorname {olla} (v)=0$
Añadir a la cola . $v$ $q$
Mientras la cola no esté vacía: $q$
1. Establezca el valor en el último elemento de la cola. $v$
2. Adiós : $U(v)>0$
  1. Para cada borde : $e=(v,w)\in \delta ^{+}(v)$
  2. ${\displaystyle f''(e)=\min\{\operatorname {pot} (e),U(v)\))$ .
  3. Actualizar _ $U(v)=U(v)-f''(e)$
  4. Actualizar _ $U(w)=U(w)+f''(e)$
  5. instalar _ $\operatorname {pot} (w)=\operatorname {pot} (w)-\operatorname {pot} (e)$
  6. Si y desencolar ._ _ ${\ estilo de visualización con \ neq t}$ $U(w)=f''(e)$ $w$ $q$

Debido a que al menos un vértice está "saturado" en cada iteración de la búsqueda de un flujo de bloqueo, se completa en las iteraciones del peor caso, cada una de las cuales considera el máximo de vértices. Sea el número de bordes "saturados" en cada -ésima iteración de la búsqueda de un hilo de bloqueo. Entonces su complejidad asintótica es , donde es el número de vértices y es el número de aristas en el gráfico. Por tanto, la complejidad asintótica del algoritmo de dispersión de Dinitz es igual a , ya que el flujo de bloqueo puede pasar como máximo por vértices. $|V|-1$ $|V|$ $l_{yo}$ $i$ $\sum_{i=1}^{n-1}O(n+l_{i})=O(n^{2}+\sum_{i=1}^{n-1}l_ {i})=O(n^{2}+m)$ $norte$ $metro$ $O(|V|^{3})$ $|V|$

Literatura

Yefim Dinitz. Algoritmo de Dinitz: la versión original y la versión de Even // Informática teórica: ensayos en memoria de Shimon Even (Inglés) / Oded Goldreich, Arnold L. Rosenberg y Alan L. Selman. - Springer, 2006. - Pág. 218-240. — ISBN 978-3540328803 .
BH Korte, Jens Vygen. 8.4 Flujos de Bloqueo y Algoritmo de Fujishige // Optimización Combinatoria: Teoría y Algoritmos (Algorithms and Combinatorics, 21 ) . - Springer Berlín Heidelberg , 2008. - Pág . 174-176 . — ISBN 978-3-540-71844-4 .

Enlaces

Algoritmo de Dinit en e-maxx.ru: Descripción, pruebas, implementación en C++