Algoritmo dinic
El algoritmo Dinic o Dinitz se basa en dos nociones: una grafico nivel y un flujo de bloqueo (gráfico de nivel y flujo de bloqueo).
Para determinar el gráfico de nivel, colocamos la fuente en el nivel 1, sus sucesores en el nivel 2, y así sucesivamente.
El flujo de bloqueo es el flujo maximo puede pasar en un camino dado.
El algoritmo de Dinic es el siguiente:
- construir un gráfico de nivel
- encontrar un camino creciente (el más pequeño) desde la fuente hasta el pozo
- encontrar el arco que limita el camino creciente
- encontrar un camino que aumenta desde la cumbre limitante hasta el pozo
- Repita los pasos 3 y 4 para construir un flujo de bloqueo hasta que ya no haya una ruta creciente.
Ejemplo
Construcción del gráfico de nivel:
Encuentre un camino creciente, encuentre el arco límite:
Regrese a los pasos 3 y 4:
Y así sucesivamente hasta no encontrar un camino creciente:
ES 
FR 
EN