contenido
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 :
Construyamos el gráfico de brechas y busquemos un ciclo negativo:
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.
ES 
FR 
EN 
RU