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 científico informático israelí (antes soviético) Yefim (Chaim) A. Dinitz. [1] El algoritmo se ejecuta entiempo y es similar al algoritmo de Edmonds-Karp , que se ejecuta entiempo, ya que utiliza las rutas de aumento más cortas. La introducción de los conceptos de gráfico de nivel y flujo de bloqueo permiten que el algoritmo de Dinic logre su desempeño.
Historia
Yefim Dinitz inventó este algoritmo en respuesta a un ejercicio previo a la clase de algoritmos de Adelson-Velsky . En ese momento, no estaba al tanto de los hechos básicos relacionados con el algoritmo Ford-Fulkerson . [2]
Dinitz menciona la invención de su algoritmo en enero de 1969, que se publicó en 1970 en la revista Doklady Akademii Nauk SSSR . En 1974, Shimon Even y (su entonces estudiante de doctorado) Alon Itai en el Technion en Haifa estaban muy curiosos e intrigados por el algoritmo de Dinitz, así como por la idea relacionada de Alexander V. Karzanov de bloquear el flujo. Sin embargo, fue difícil para ellos descifrar estos dos documentos, cada uno limitado a cuatro páginas para cumplir con las restricciones de la revista Doklady Akademii Nauk SSSR . Even no se rindió, y después de tres días de esfuerzo logró entender ambos papeles, excepto el tema del mantenimiento de la red por capas. Durante los dos años siguientes, 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 la forma en que el algoritmo se presenta ahora comúnmente. [3]
Durante aproximadamente 10 años después de que se inventó el algoritmo de Ford-Fulkerson, se desconocía si se podía hacer que terminara en tiempo polinomial 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) mostraron 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 es decreciente y el algoritmo siempre termina.
Definición
Dejar ser una red con y la capacidad y el flujo del borde , respectivamente.
- La capacidad residual es un mapeo definido como,
- Si ,
- de lo contrario.
- Si ,
- El gráfico residual es un gráfico no ponderado , dónde
- .
- Un camino de aumento es un - ruta en el gráfico residual .
- Definir ser la longitud del camino más corto desde a en . Entonces el gráfico de nivel de es el grafico , dónde
- .
Algoritmo
Algoritmo de Dinic
- Entrada : una red .
- Salida : An - flujo de valor máximo.
- Colocar para cada .
- Construir de de . Si, parada y salida .
- Encuentra un flujo de bloqueo en .
- Agregar flujo de aumento por y vuelva al paso 2.
Análisis
Se puede demostrar que el número de capas en cada flujo de bloqueo aumenta en al menos 1 cada vez y, por lo tanto, hay como máximo Bloqueo de flujos en el algoritmo. Para cada uno de ellos:
- el gráfico de nivel se puede construir mediante una búsqueda en amplitud en hora
- un flujo de bloqueo en el gráfico de nivel puede encontrarse en hora
con tiempo total de funcionamiento para cada capa. Como consecuencia, el tiempo de ejecución del algoritmo de Dinic es. [6]
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 para .
Casos especiales
En las redes con capacidades unitarias, se mantiene un límite de tiempo mucho más fuerte. Cada flujo de bloqueo se puede encontrar en tiempo, y se puede demostrar que el número de fases no excede y . Por lo tanto, el algoritmo se ejecuta enhora. [7]
En las redes que surgen del problema de emparejamiento bipartito , el número de fases está limitado por, lo que lleva a la limitados en el tiempo. El algoritmo resultante también se conoce como algoritmo 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 la fuente y el sumidero, tiene un solo borde de entrada de capacidad uno, o un solo borde de salida de capacidad uno, y todas las demás capacidades son números enteros arbitrarios. . [5]
Ejemplo
La siguiente es una simulación del algoritmo de Dinic. En el gráfico de nivel, los vértices con etiquetas en rojo son los valores . Los caminos en azul forman un flujo de bloqueo.
1. | |||
---|---|---|---|
El flujo de bloqueo consta de
Por tanto, el flujo de bloqueo es de 14 unidades y el valor del flujo es 14. Tenga en cuenta que cada camino de aumento en el flujo de bloqueo tiene 3 bordes. | |||
2. | |||
El flujo de bloqueo consta de
Por tanto, el flujo de bloqueo es de 5 unidades y el valor del flujo es 14 + 5 = 19. Tenga en cuenta que cada trayecto de aumento tiene 4 aristas. | |||
3. | |||
Desde no se puede alcanzar en , el algoritmo termina y devuelve un flujo con un valor máximo de 19. Tenga en cuenta que en cada flujo de bloqueo, el número de bordes en la ruta de aumento aumenta en al menos 1. |
Ver también
Notas
- ^ Yefim Dinitz (1970). "Algoritmo para la 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.
- ^ Ilan Kadar; Sivan Albagli (27 de noviembre de 2009). "Algoritmo de Dinitz para encontrar un flujo máximo en una red" .
- ^ Yefim Dinitz. "Algoritmo de Dinitz: la versión original y la versión de Even" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Esto significa que el subgrafo resultante de eliminar todos los bordes saturados (es decir, todos los bordes tal que ) no contiene ninguna ruta de a . En otros términos, el flujo de bloqueo es tal que todos los caminos posibles desde a contiene un borde saturado.
- ↑ a b Tarjan 1983 , p. 102.
- ^ Yefim Dinitz (2006). "Algoritmo de Dinitz: la versión original y la versión de Even" (PDF) . 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.
- ^ Incluso, Shimon; Tarjan, R. Endre (1975). "Flujo de red y conectividad de gráficos de prueba". Revista SIAM de Computación . 4 (4): 507–518. doi : 10.1137 / 0204043 . ISSN 0097-5397 .
Referencias
- Yefim Dinitz (2006). "Algoritmo de Dinitz: la versión original y la versión de Even" (PDF) . 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.
- Tarjan, RE (1983). Estructuras de datos y algoritmos de red .
- BH Korte; Jens Vygen (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.