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 :
vamos a construirlo grafico brecha y busque 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