Algorithme de Ford-Fulkerson

Contenus

L’algorithme de Ford-Fulkerson cherche un chemin augmentant dans le graphe résiduel. Il sature ce chemin s’il existe, sinon il retourne le flot maximum. Plus précisément, l’algorithme établit une coupe minimal pour vérifier le critère d’optimalité. On rappelle que le flot est inférieur ou égale à la coupe.

Afin d’initialiser l’algorithme, il est possible d’attribuer un flot quelconque dans le graphe en suivant des chemins simples (de la source vers le puits). Dans le schéma suivant, nous avons pris pour initialisation le chemin s-2-3-t.

algorithme de ford-fulkerson flot maximum max flow problem coupe minimale graphe d'écart flot augmentant

Après construction du graphe d’écart (residual graph en anglais), un chemin de s à t est choisi s’il en existe. Sinon nous avons le flot maximal. Dans le premier cas, le nouveau flot est calculé suivant le chemin augmentant choisi dans le graphe d’écart: on rajoute le flot du chemin augmentant au flot existant si l’arc correspondant dans le graphe d’origine est dans le même sens que celui du graphe d’écart, sinon on soustrait le flot.L’algorithme s’arrête lorsqu’il n’y a plus de chemin augmentant.

Il est possible de former une coupe à l’aide du dernier graphe d’écart. On applique un parcours à partir de s, tous les sommets pouvant être parcouru sont dans l’ensemble S, les autres dans l’ensemble T. En effet, les arcs saturés par le flots coupent le graphe en deux sous-ensembles, et forment la valeur de la coupe.

flot maximum max flow problem coupe minimale graphe d'écart flot augmentant algorithme de ford-fulkerson

Si l’on souhaite augmenter le flot par un changement de valeur, il faudra augmenter le flot maximum pouvant passer par ces arcs.

L’algorithme de Ford-Fulkerson pas à pas

Le flot initial est de 0. Ici le graphe résiduel G_f est une copie du graphe G. Nous cherchons un chemin de s à t, par exemple s-2-5-t:

La valeur minimal du chemin est de 8.Nous rajoutons ce flot de 8 sur le chemin dans le graphe G.

Pour rappel le graphe résiduel doit montrer les arcs inverses (représentant les flots). Le graphe résiduel de la nouvelle itération est le suivant :

Ici nous choisissons le chemin s-2-3-5-t, avec 2 pour flot bloquant. Lorsque on choisit un arc inverse (donc représentant un flot) le nouveau flot dans le graphe G est réduit comme le montre ce nouveau graphe G.