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.
Compartir, repartir :
- Haga clic para compartir en Twitter (Se abre en una nueva ventana)
- Haga clic para compartir en Facebook (Se abre en una nueva ventana)
- Haga clic para compartir en LinkedIn (Se abre en una nueva ventana)
- Haga clic para imprimir (Se abre en una nueva ventana)
- Haga clic para compartir en WhatsApp (Se abre en una nueva ventana)
- Haz clic para enviar un enlace por correo electrónico a un amigo (Se abre en una nueva ventana)