Cycle-canceling algorithm

L’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 :

cca1

Construisons le graphe d’écart et cherchons un cycle négatif :

cca2

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.

 

Publicités