Algoritmo de cancelación de ciclo

Algoritmo de cancelación de ciclo

El algoritmo de cancelación de ciclo comienza con la máxima resolución de flujo. Luego, de manera iterativa, 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 ya no hay un ciclo negativo, el algoritmo finaliza.

Ejemplo :

algoritmo de cancelación de ciclo

Construyamos el gráfico de brechas y busquemos un ciclo negativo:

algoritmo 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
es_ESES
A los bloggers de %d les gusta esto: