Recherche de la première chaîne améliorante
On examine ici le point 0 qui passe de vert clair à vert foncé sur la représentation graphique pour indiquer que l'on est en train de l'examiner.
A la fin de son examen, il disparaîtra de la tête de la file et deviendra violet pour point marqué et examiné.
Les successeurs du point 0 sont le point 1 avec une capacité de 4 pour l'arc (0,1) et le point 4 avec une capacité de 3, aussi, on ajoute en queue de file les points 1 et 4, on les colorie en vert clair pour indiquer qu'ils sont marqués, mais non encore examinés. Origine(1) et Origine(4) prennent la valeur 0 puisqu'ils sont été marqués à partir de 0. Delta(1) vaut 4 (la capacité de l'arc) et Delta(4) vaut 3 (la capacité de l'arc).
Le point 0 a disparu de la tête de la file et est devenu violet.
La tête de la file est le point 1.
Il a pris la couleur vert foncé pour indiquer que l'on commence de l'examiner.
Il a un seul successeur, le point 2, que l'on met à la queue de la file et que l'on colorie en vert clair.
Origine(2) prend la valeur 1 et Delta(2) est égal à 4 le minimum entre Delta(1) et la capacité de l'arc (1,2).
Le point 1 a disparu de la file et est devenu violet (marqué et examiné).
Le point 4 est la nouvelle tête de la file, en cours d'examen et donc vert foncé.
Il a pour successeurs les points 3 et 5 que l'on met à la queue de la file et que l'on colorie en vert clair.
Origine(3) et Origine(5) prennent la valeur 4 et Delta(3) et Delta(5) sont égaux à 3 le minimum entre Delta(4) et la capacité de l'arc (4,3) ou de l'arc (4,5).
Le point 4 a disparu de la file et est devenu violet (marqué et examiné).
Le point 2 est la nouvelle tête de la file, en cours d'examen et donc en vert foncé.
Il a un seul successeur qui est le point 3, mais le point 3 en vert clair a déjà été marqué par le point 4.
Le point 2 ne permet donc pas de trouver de nouvelle propagation pour l'augmentation potentielle du flot.
Le point 2 a disparu de la file et est devenu violet (marqué et examiné).
Le point 3 est la nouvelle tête de la file, en cours d'examen et donc en vert foncé.
Il a un seul successeur qui est le point 7, c'est à dire le puits qui est mis en vert clair.
Origine(7) est égal à 3 et Delta(7) est égal à 3, le minimum de Delta(3) et de la capacité de l'arc (3,7).
Première chaîne améliorante trouvée
Comme on a marqué le puits avec une valeur Delta(7) égale à 3, on sait que l'on a une chaîne améliorante qui va de la source 0 au puits 7 sur laquelle on va pouvoir augmenter les capacités de 3.
Pour trouver la chaîne améliorante, comme pour les problèmes de cheminement avec marquage, on "remonte" le tableau Origine.
Origine(7) = 3 : le dernier arc de la chaîne améliorante est l'arc (3,7).
Origine(3) = 4 : l'avant dernier arc de la chaîne améliorante est l'arc (4,3).
Origine(4) = 0 : le premier arc de la chaîne améliorante est l'arc (0,4).
On peut donc augmenter la capacité de 3 sur le chemin { 0, 4, 3, 7}.
Mise à jour des capacités et effacement des marques
Sur le chemin améliorant, le flot sur les arcs passe de 0 à 3.
On ne peut plus augmenter le flux sur les arcs de ce chemin.
Les arcs (0,4), (4,3) et (3,7) sont saturés et coloriés en rouge rosé.
Attention : PENSER A EFFACER LES MARQUES
Comme on a changé la valeur des flux sur les arcs, les marques qui étaient inscrites dans les tableaux Delta et Origine n'ont plus aucune signification et il ne faut surtout pas oublier de les effacer.
C'est pourquoi, avant de chercher une nouvelle chaîne améliorante, on efface la file qui est réinitialisée avec la source et on remet tous les Delta à 0 et les valeurs de Origine n'ont plus aucun intérêt, sauf pour la source où Delta(0) vaut +∞ et Origine(0) vaut "##".
