algoritmo de dinic

El algoritmo de Dinic o algoritmo de Dinitz es un algoritmo fuertemente polinomial para calcular el flujo máximo en una red de flujo , concebido en 1970 por el informático israelí (ex soviético) Yefim Dinitz . ^[1] El algoritmo se ejecuta en el tiempo y es similar al algoritmo de Edmonds-Karp , que se ejecuta en el tiempo, en el sentido de que utiliza rutas de aumento más cortas. La introducción de los conceptos de gráfico de niveles y flujo de bloqueo permite que el algoritmo de Dinic alcance su rendimiento. ${\displaystyle O(|V|^{2}|E|)}$ ${\displaystyle O(|V||E|^{2})}$

Historia

Dinitz inventó el algoritmo en enero de 1969, como estudiante de maestría en el grupo de Georgy Adelson-Velsky . Unas décadas más tarde, recordaría: ^[2]

En la clase de Algoritmos de Adel'son-Vel'sky, el profesor tenía la costumbre de presentar el problema para discutirlo en la siguiente reunión como ejercicio a los estudiantes. El DA se inventó en respuesta a tal ejercicio. En ese momento, el autor no estaba al tanto de los hechos básicos relacionados con [el algoritmo Ford-Fulkerson ]….

⋮

La ignorancia a veces tiene sus méritos. Muy probablemente, el DA no se habría inventado entonces, si el autor hubiera conocido la idea de una posible desaturación del borde saturado.

En 1970, Dinitz publicó una descripción del algoritmo en Doklady Akademii Nauk SSSR . En 1974, Shimon Even y (su entonces estudiante de doctorado) Alon Itai en el Technion de Haifa sentían mucha curiosidad e intriga por el algoritmo de Dinitz, así como por la idea relacionada de Alexander V. Karzanov de bloquear el flujo. Sin embargo, les resultó difícil descifrar estos dos artículos, ya que cada uno estaba limitado a cuatro páginas para cumplir con las restricciones de la revista Doklady Akademii Nauk SSSR . Incluso no se dio por vencido y después de tres días de esfuerzo logró comprender ambos documentos excepto el tema del mantenimiento de la red en capas. Durante los siguientes dos años, Even dio conferencias sobre el "algoritmo de Dinic", pronunciando mal el nombre del autor mientras lo popularizaba. Even e Itai también contribuyeron a este algoritmo combinando BFS y DFS , que es como ahora se presenta comúnmente el algoritmo. ^[2]

Durante aproximadamente 10 años después de que se inventó el algoritmo Ford-Fulkerson, se desconocía si se podía hacer que terminara en tiempo polinómico en el caso general de capacidades de borde irracionales. Esto provocó la falta de un algoritmo de tiempo polinómico conocido para resolver el problema de flujo máximo en casos genéricos. El algoritmo de Dinitz y el algoritmo de Edmonds-Karp (publicado en 1972) demostraron de forma independiente que en el algoritmo de Ford-Fulkerson, si cada camino de aumento es el más corto, entonces la longitud de los caminos de aumento no disminuye y el algoritmo siempre termina.

Definición

Sea una red con y la capacidad y el flujo del borde , respectivamente. ${\displaystyle G=((V,E),c,f,s,t)}$ ${\displaystyle c(u,v)}$ ${\displaystyle f(u,v)}$ ${\displaystyle (u,v)}$

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

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

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

2. si , ${\displaystyle (v,u)\in E}$

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

3. ${\displaystyle c_{f}(u,v)=0}$de lo contrario.

La gráfica residual es una gráfica no ponderada , donde ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$

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

Una ruta creciente es una ruta – en el gráfico residual . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle G_{f}}$

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

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

Un flujo de bloqueo es un flujo tal que el gráfico no contiene ninguna ruta . ^{[Nota 1] [3]} ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle f'}$ ${\displaystyle G'=((V,E_{L}'),s,t)}$ ${\displaystyle E_{L}'=\{(u,v)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ ${\displaystyle s}$ ${\displaystyle t}$

Algoritmo

Algoritmo de Dinic

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

Salida : An – flujo de valor máximo. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle f}$

1. Establecer para cada uno . ${\displaystyle f(e)=0}$ ${\displaystyle e\in E}$
2. Construir a partir de . Si , deténgase y emita . ${\displaystyle G_{L}}$ ${\displaystyle G_{f}}$ ${\displaystyle G}$ ${\displaystyle \operatorname {dist} (t)=\infty }$ ${\displaystyle f}$
3. Encuentre un flujo de bloqueo en . ${\displaystyle f'}$ ${\displaystyle G_{L}}$
4. Agregue flujo de aumento y vuelva al paso 2. ${\displaystyle f}$ ${\displaystyle f'}$

Análisis

Se puede demostrar que el número de capas en cada flujo de bloqueo aumenta al menos en 1 cada vez y, por lo tanto, hay como máximo flujos de bloqueo en el algoritmo. Para cada uno de ellos: ${\displaystyle |V|-1}$

• El gráfico de niveles se puede construir mediante una búsqueda en amplitud en el tiempo. ${\displaystyle G_{L}}$ ${\displaystyle O(E)}$
• se puede encontrar un flujo de bloqueo en el gráfico de nivel en el tiempo ^{[Nota 2]} ${\displaystyle G_{L}}$ ${\displaystyle O(VE)}$

con el tiempo total de ejecución de cada capa. Como consecuencia, el tiempo de ejecución del algoritmo de Dinic es . ^[2] ${\displaystyle O(E+VE)=O(VE)}$ ${\displaystyle O(V^{2}E)}$

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

Casos especiales

En redes con capacidades unitarias, se aplica un límite de tiempo mucho más estricto. Cada flujo de bloqueo se puede encontrar en el tiempo y se puede demostrar que el número de fases no excede y . ^{[Nota 3]} Por lo tanto, el algoritmo se ejecuta en el tiempo. ^[4] ${\displaystyle O(E)}$ ${\displaystyle O({\sqrt {E}})}$ ${\displaystyle O(V^{2/3})}$ ${\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}$

En las redes que surgen del problema de coincidencia bipartita , el número de fases está limitado por , lo que conduce a un límite de tiempo. El algoritmo resultante también se conoce como algoritmo de Hopcroft-Karp . De manera más general, este límite es válido para cualquier red unitaria : una red en la que cada vértice, excepto el origen y el sumidero, tiene un único borde de entrada de capacidad uno o un único borde de salida de capacidad uno, y todas las demás capacidades son números enteros arbitrarios. . ^[3] ${\displaystyle O({\sqrt {V}})}$ ${\displaystyle O({\sqrt {V}}E)}$

Ejemplo

La siguiente es una simulación del algoritmo de Dinic. En el gráfico de niveles , los vértices con etiquetas en rojo son los valores . Los caminos en azul forman un flujo de bloqueo. ${\displaystyle G_{L}}$ ${\displaystyle \operatorname {dist} (v)}$

Ver también

• Algoritmo de Ford-Fulkerson
• Problema de flujo máximo

Notas

1. Esto significa que el subgrafo resultante de eliminar todos los bordes saturados (bordes con ) no contiene ninguna ruta desde hasta . En otros términos, el flujo de bloqueo es tal que cada camino posible desde hasta contiene un borde saturado. ${\displaystyle (u,v)}$ ${\displaystyle f'(u,v)=c_{f}|_{E_{L}}(u,v)}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$
2. Encontrar el flujo de bloqueo se puede implementar por ruta mediante una secuencia de operaciones de avance y retirada. Consulte http://courses.csail.mit.edu/6.854/06/scribe/scribe11.pdf para obtener más detalles. ${\displaystyle O(E)}$
3. El límite supone que no hay dos aristas que conecten el mismo par de vértices en la misma dirección, mientras que el límite no asume tal suposición. ${\displaystyle O(V^{2/3})}$ ${\displaystyle O({\sqrt {E}})}$

1. EA Dinic (1970). «Algoritmo para solución de un problema de caudal máximo en una red con estimación de potencia» (PDF) . Doklady Akademii Nauk SSSR . 11 : 1277-1280.
2. Dinitz, Yefim (2006). "Algoritmo de Dinitz: la versión original y la versión de Even". En Oded Goldreich ; Arnold L. Rosenberg ; Alan L. Selman (eds.). Informática teórica: ensayos en memoria de Shimon Even . Saltador. págs. 218-240. ISBN 978-3-540-32880-3.
3. Tarjan 1983, pag. 102.
4. Incluso, Shimón; Tarjan, R. Endre (1975). "Flujo de red y prueba de conectividad de gráficos". Revista SIAM de Computación . 4 (4): 507–518. doi :10.1137/0204043. ISSN  0097-5397.

Referencias

• Dinitz, Yefim (2006). "Algoritmo de Dinitz: la versión original y la versión de Even". En Oded Goldreich ; Arnold L. Rosenberg ; Alan L. Selman (eds.). Informática teórica: ensayos en memoria de Shimon Even . Saltador. págs. 218-240. ISBN 978-3-540-32880-3.
• Kadar, Ilán; Albagli, Sivan (18 de abril de 2019). Algoritmo de Dinitz para encontrar un flujo máximo en una red. Universidad Ben Gurión. Archivado desde el original el 22 de diciembre de 2023.
• Korte, BH; Vygen, Jens (2008). "8.4 Bloqueo de flujos y algoritmo de Fujishige". Optimización combinatoria: teoría y algoritmos (Algoritmos y combinatoria, 21) . Springer Berlín Heidelberg. págs. 174-176. ISBN 978-3-540-71844-4.
• Tarjan, RE (1983). Estructuras de datos y algoritmos de red .