Algoritmo dinic

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.

gráfico de nivel de dinitz del algoritmo dinic

El flujo de bloqueo es el flujo maximo puede pasar en un camino dado.

gráfico de nivel de dinitz del algoritmo dinic

El algoritmo de Dinic es el siguiente:

  1. construir un gráfico de nivel
  2. encontrar un camino creciente (el más pequeño) desde la fuente hasta el pozo
  3. encontrar el arco que limita el camino creciente
  4. encontrar un camino que aumenta desde la cumbre limitante hasta el pozo
  5. 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:

gráfico de nivel de dinitz del algoritmo dinic

Encuentre un camino creciente, encuentre el arco límite:

gráfico de nivel de dinitz del algoritmo dinic

Regrese a los pasos 3 y 4:

gráfico de nivel de dinitz del algoritmo dinic

Y así sucesivamente hasta no encontrar un camino creciente:

gráfico de nivel de dinitz del algoritmo dinic
Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: