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 la trayectoria 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 no haya una ruta creciente
Ejemplo
Construcción del gráfico de nivel:
Encuentre la ruta creciente, encuentre el arco limitante:
Volver a los pasos 3 y 4:
Y así sucesivamente hasta que no se encuentre más camino creciente:
