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: .
Sea una red de transporte , en la que y son, respectivamente, el rendimiento y el flujo a través del borde .
El ancho de banda residual es un mapeo definido como:algoritmo de Dinit
Entrada : Red . Salida : caudal máximo .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 .
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 .
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.
una. | |||
---|---|---|---|
Un hilo de bloqueo consta de rutas:
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. | |||
2. | |||
Un hilo de bloqueo consta de rutas:
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. | |||
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. |
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.
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 .
Entrada : Red . Salida : caudal máximo .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:
Entrada : Red auxiliar , vértice tal que . Salida : un flujo desde el origen hasta el vértice que forma parte de un flujo de bloqueo.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.