Algorithme de Ford-Fulkerson

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.

flow2

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.

cut3.png

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 pas à pas

ford1

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

ford2

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

ford3

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 :

ford4

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.

ford5

Valeur du flot = 10. Etc…

ford6ford7

Valeur du flot = 16

ford8

Choix de l’arc inverse (3,2) :

ford9

Valeur du flot = 18.

ford10ford11

Valeur du flot = 19.

ford12

Il n’existe plus de chemin de s à t, nous avons trouvé un flot maximal pour ce graphe G.

 

Publicités