Algoritmo de cancelación de ciclo

Algoritmo de cancelación de ciclo

La cancelación del ciclo algoritmo comienza con una resolución de flujo maximo. Luego, iterativamente, el algoritmo busca un ciclo con un costo negativo (costo negativo si el borde se toma en la dirección opuesta al flujo) y aumenta el flujo en este ciclo. Cuando no hay más ciclos negativos, el algoritmo finaliza.

Ejemplo :

algoritmo de ciclo negativo de cancelación de ciclo

vamos a construirlo grafico brecha y busque un ciclo negativo:

algoritmo de ciclo negativo de cancelación de ciclo

El ciclo 4-2-3-4 tiene un costo de -3 + 1 + 1 = -1, podemos saturarlo con un flujo de 2.

De manera similar con el ciclo 4-2-1-3-4 con un costo de -3-2 +2 +1 = -2, podemos saturarlo con un flujo de 1.

Ya no hay un ciclo negativo, finaliza el algoritmo.

Compartir, repartir