Algorithme de Ford-Fulkerson

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.

algorithme de Ford-Fulkerson graphe d'écart
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.

algorithme de Ford-Fulkerson graphe d'écart

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

algorithme de Ford-Fulkerson graphe d'écart

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

algorithme de Ford-Fulkerson graphe d'écart

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

algorithme de Ford-Fulkerson graphe d'écart

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 :

algorithme de Ford-Fulkerson graphe d'écart

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.

algorithme de Ford-Fulkerson graphe d'écart

Valeur du flot = 10. Etc…

algorithme de Ford-Fulkerson graphe d'écart
algorithme de Ford-Fulkerson graphe d'écart

Valeur du flot = 16

algorithme de Ford-Fulkerson graphe d'écart

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

algorithme de Ford-Fulkerson graphe d'écart

Valeur du flot = 18.

algorithme de Ford-Fulkerson graphe d'écart
algorithme de Ford-Fulkerson graphe d'écart

Valeur du flot = 19.

algorithme de Ford-Fulkerson graphe d'écart

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

Делиться
ru_RURU
%d такие блоггеры, как: