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.^[1]​ El algoritmo es ejecutado en un tiempo de ${\displaystyle O(V^{2}E)}$ y está basado en el Algoritmo de Edmonds-Karp, el cual a su vez se ejecuta en un tiempo ${\displaystyle 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.

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

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

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

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

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

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

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

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

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

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

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

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

Algoritmo de Dinic

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

Salida: Un flujo ${\displaystyle s-t}$ de valor ${\displaystyle f}$ maximizado.

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

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 ${\displaystyle n-1}$ bloqueos de flujo en el algoritmo, donde ${\displaystyle n}$ es el número de vértices en la red. El nivel del grafo ${\displaystyle G_{L}}$ puede ser construido por búsqueda en anchura en un tiempo de ${\displaystyle O(E)}$ y un bloqueo de flujo en cada nivel del grafo puede ser encontrado en un tiempo de ${\displaystyle O(VE)}$. Por lo tanto, el tiempo del algoritmo de Dinic es de ${\displaystyle 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 ${\displaystyle O(E\log V)}$ y por lo tanto el tiempo de ejecución del algoritmo de Dinic puede ser reducido a ${\displaystyle O(VE\log V)}$.

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 ${\displaystyle O(E)}$, y es demostrable que el número de fases no excedan ${\displaystyle O({\sqrt {E}})}$ y ${\displaystyle O(V^{2/3})}$. En estos casos el algoritmo se ejecuta en un tiempo de ${\displaystyle 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 ${\displaystyle O({\sqrt {V}})}$,lo cual resulta en un limitado tiempo de ${\displaystyle 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.^[2]​

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

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	El bloqueo de flujo está constituido por ${\displaystyle \{s,1,3,t\}}$ con 4 unidades de flujo, ${\displaystyle \{s,1,4,t\}}$ con 6 unidades de flujo, and ${\displaystyle \{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 ${\displaystyle |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 ${\displaystyle \{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 ${\displaystyle |f|}$ es 14 + 5 = 19. Note que cada ruta de aumento en el flujo de bloqueo tiene 4 arcos.
3.
	Desde ${\displaystyle t}$ no puede ser alcanzado en ${\displaystyle 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.

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.

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

• 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.