computer network) con complejidad O(V E2).
Es asintóticamente más lento que el algoritmo de Push-relabel, que tiene complejidad O(V3), pero es habitualmente más rápido en la práctica para grafos ralos.
El algoritmo fue publicado por primera vez por un científico soviético, Yefim (Chaim) Dinic, en 1970,[1] e independientemente por Jack Edmonds y Richard Karp en 1972.
[2] El Algoritmo de Dinic incluye técnicas adicionales para reducir la complejidad a O(V2E).
El algoritmo es idéntico al algoritmo de Ford-Fulkerson, excepto porque el orden para ir buscando los caminos aumentantes está definido.
El camino encontrado debe ser el camino más corto que tiene capacidad disponible.
Esto se puede encontrar mediante una búsqueda en anchura, ya que dejamos que los bordes tengan unidad de longitud.
La complejidad O(V E2)[3] se fundamenta mostrando que cada camino aumentante puede ser encontrado con O(E), cada vez que al menos uno de los lados E se satura, la distancia desde el lado saturado hasta el origen a través del camino aumentante deberá ser más largo que la última vez que este estuvo saturado, y ese largo es a lo sumo V.
Otra propiedad de este algoritmo es que el largo del camino aumentante más corto se incrementa monotonamente.
[4] Dado un grafo dirigido (network) de 7 nodos, origen A, hundimiento G, y las capacidades que se muestran debajo:
, la capacidad total, menos el flujo que está en uso.
es negativo, esto contribuye a la capacidad del residuo.
Notar como la longitud del Camino Aumentante encontrado por el algoritmo nunca se decrementa.
Los caminos encontrados son lo más cortos posibles.
El flujo encontrado es igual a la capacidad a travès de corte mínimo en el grafo separando el origen del hundimiento.
Hay un solo corte minimal en este grafo, particionando los nodos en los conjuntos