y está basado en el Algoritmo de Edmonds-Karp, el cual a su vez se ejecuta en un tiempo
, y utiliza trayectorias de aumento más cortas.
{\displaystyle G=((V,E),c,s,t)}
que será una red de flujo con
Algoritmo de Dinic 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
bloqueos de flujo en el algoritmo, donde
es el número de vértices en la red.
puede ser construido por búsqueda en anchura en un tiempo de
y un bloqueo de flujo en cada nivel del grafo puede ser encontrado en un tiempo de
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
y por lo tanto el tiempo de ejecución del algoritmo de Dinic puede ser reducido a
En redes con capacidades de unidad, el tiempo de ejecución es mucho mayor.
, y es demostrable que el número de fases no excedan
En estos casos el algoritmo se ejecuta en un tiempo de
En las redes surgidas durante la solución del problema de apareamiento, el número de fases está limitado por
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.
, los vértices marcados en rojo son los valores
Las rutas en azul forman el bloqueo de flujo.
El bloqueo de flujo está constituido por Por lo tanto el bloqueo del flujo es de 14 unidades y el valor del flujo
Note que cada ruta de aumento en el flujo de bloqueo tiene 3 arcos.
El bloqueo de flujo está constituido por Por lo tanto el bloqueo del flujo es de 5 unidades y el valor del flujo
Note que cada ruta de aumento en el flujo de bloqueo tiene 4 arcos.
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.