Algoritmo de Dinic

El algoritmo de Dinic es un algoritmo de Tiempo polinómico para la computación de un Flujo maximal en una red de flujo, concebida en 1970 por el científico de la computación Yefim Dinitz, israelí de origen soviético.​ El algoritmo es ejecutado en un tiempo de $O(V^{2}E)$ y está basado en el Algoritmo de Edmonds-Karp, el cual a su vez se ejecuta en un tiempo $O(VE^{2})$, y utiliza trayectorias de aumento más cortas. La introducción de los conceptos nivel de grafo y bloqueo de flujo es lo que define el rendimiento del algoritmo de Dinic.

Definición

Se tiene el grafo $G=((V,E),c,s,t)$ que será una red de flujo con $c(u,v)$ es la capacidad y $f(u,v)$ el flujo del arco $(u,v)$.

La capacidad residual es un mapeo $c_{f}:V\times V\to R^{+}$ definido como,

1. Si $(u,v)\in E$,

   $c_{f}(u,v)=c(u,v)-f(u,v)$

   $c_{f}(v,u)=f(u,v)$

2. $c_{f}(u,v)=0$ de otra manera.

El grafo residual es el grafo $G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)$, donde

$E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}$.

La trayectoria de aumento es una ruta $s-t$ en el grafo residual $G_{f}$.

Se define $\operatorname {dist} (v)$ como la longitud del camino más corto desde $s$ hasta $v$ en $G_{f}$.Entonces el nivel del grafo de $G_{f}$ es el grafo $G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)$, donde

$E_{L}=\{(u,v)\in E_{f}:\operatorname {dist} (v)=\operatorname {dist} (u)+1\}$.

El bloqueo del flujo es un $s-t$ flujo $f$ de manera tal que el grafo $G'=(V,E_{L}',s,t)$ con $E_{L}'=\{(u,v):f(u,v)<c_{f}|_{E_{L}}(u,v)\}$ no tiene ninguna ruta $s-t$.

Algoritmo

Algoritmo de Dinic

Entrada: Una red $G=((V,E),c,s,t)$.

Salida: Un flujo $s-t$ de valor $f$ maximizado.

1. Se tiene $f(e)=0$ para cada $e\in E$.
2. Construir$G_{L}$ desde $G_{f}$ de $G$. Si $\operatorname {dist} (t)=\infty$, detener y retornar el resultado $f$.
3. Encontrar un bloqueo de flujo $f\;'$ en $G_{L}$.
4. Aumentar el flujo $\ f$ by $f\;'$ y volver al paso 2.

Análisis

Se puede demostrar que el número de arcos en cada bloqueo de flujo, es incrementado en al menos 1 unidad cada vez, y por lo tanto hay al menos $n-1$ bloqueos de flujo en el algoritmo, donde $n$ es el número de vértices en la red. El nivel del grafo $G_{L}$ puede ser construido por búsqueda en anchura en un tiempo de $O(E)$ y un bloqueo de flujo en cada nivel del grafo puede ser encontrado en un tiempo de $O(VE)$. Por lo tanto, el tiempo del algoritmo de Dinic es de $O(V^{2}E)$.

Usando una estructura de datos llamada árboles dinámicos, el tiempo de ejecución para encontrar un bloqueo de flujo en cada fase puede ser reducido a $O(E\log V)$ y por lo tanto el tiempo de ejecución del algoritmo de Dinic puede ser reducido a $O(VE\log V)$.

Casos Especiales

En redes con capacidades de unidad, el tiempo de ejecución es mucho mayor. Cada bloqueo de flujo puede ser encontrado en un tiempo de $O(E)$, y es demostrable que el número de fases no excedan $O({\sqrt {E}})$ y $O(V^{2/3})$. En estos casos el algoritmo se ejecuta en un tiempo de $O(\min(V^{2/3},E^{1/2})E)$.

En las redes surgidas durante la solución del problema de apareamiento, el número de fases está limitado por $O({\sqrt {V}})$,lo cual resulta en un limitado tiempo de $O({\sqrt {V}}E)$. El algoritmo resultante a raíz de esto es conocido como algoritmo Hopcroft–Karp. De manera más general, este límite se mantiene para cualquier red unitaria — un tipo de red en la que cada vértice, excepto para los vértices fuente y sumidero, o bien tienen un único arco de capacidad, o un único arco con salida, y todas las demás capacidades son valores enteros arbitrarios.​

Ejemplo

Esta es una simulación del algoritmo de Dinic. En el nivel del grafo $G_{L}$, los vértices marcados en rojo son los valores $\operatorname {dist} (v)$. Las rutas en azul forman el bloqueo de flujo.

	$G$	$G_{f}$	$G_{L}$
1.
	El bloqueo de flujo está constituido por $\{s,1,3,t\}$ con 4 unidades de flujo, $\{s,1,4,t\}$ con 6 unidades de flujo, and $\{s,2,4,t\}$ con 4 unidades de flujo. Por lo tanto el bloqueo del flujo es de 14 unidades y el valor del flujo $|f|$ es 14. Note que cada ruta de aumento en el flujo de bloqueo tiene 3 arcos.
2.
	El bloqueo de flujo está constituido por $\{s,2,4,3,t\}$ con 5 unidades de flujo. Por lo tanto el bloqueo del flujo es de 5 unidades y el valor del flujo $|f|$ es 14 + 5 = 19. Note que cada ruta de aumento en el flujo de bloqueo tiene 4 arcos.
3.
	Desde $t$ no puede ser alcanzado en $G_{f}$. El algoritmo termina y retorna un valor m'aximo de flujo de 19. Note que en cada bloqueo de flujo, el n'umero de arcos en la ruta de aumento se incrementa en al menos 1 valor.

Historia

El algoritmo de Dinic fue publicado en 1970 por el ex ruso científico de la computación Yefim (Chaim) A. Dinitz , quien hoy es miembro del departamento de Ciencias de la Computación en Universidad Ben-Gurión del Néguev (Israel). Dicha publicación se realizó antes que la del algoritmo de Edmonds-Karp, el cual fue publicado en 1972, pero fue descubierta antes. Ambos demostraron cada uno por su cuenta, que en el algoritmo de Ford-Fulkerson, si cada ruta de aumento es la más corta, el largo de la ruta de aumento es no decreciente.

Véase también

• Algoritmo de Ford-Fulkerson
• Problema de Flujo Máximo ()

Referencias

• Yefim Dinitz (2006). «Dinitz' Algorithm: The Original Version and Even's Version». En Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman, ed. Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218-240. ISBN 978-3540328803. Archivado desde el original el 20 de agosto de 2016. Consultado el 22 de abril de 2012. 
• Tarjan, R. E. (1983). Data structures and network algorithms. 
• B. H. Korte, Jens Vygen (2008). «8.4 Blocking Flows and Fujishige's Algorithm». Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 174–176. ISBN 978-3-540-71844-4. 

• Datos: Q730933