Cycle-canceling algorithme
Le cycle-canceling algorithme commence par une résolution de flot maximum. Puis, de façon itérative, l’algorithme cherche un cycle avec un coût négatif (coût négatif si l’arête est prise en sens inverse du flot) et augmente le flot sur ce cycle. Lorsqu’il n’y a plus de cycle négatif, l’algorithme se termine.
Exemple :
Construisons le graphe d’écart et cherchons un cycle négatif :
Le cycle 4-2-3-4 a un cout de -3 + 1 + 1 = -1, on peut le saturer avec un flot de 2.
De même avec le cycle 4-2-1-3-4 avec un cout de -3 -2 +2 +1 = -2, on peut le saturer avec un flot de 1.
Il n’y a plus de cycle négatif, l’algorithme se termine.
FR 
EN 
ES