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.

Publicités