216
Recherche opérationnelle
Si
admet un flot saturant ce flot est de coût minimum. En effet :
a) est un flot de
b) On a
Par ailleurs, sur , on a
et
Tous les sommets et les sommets sont utilisés puisque est saturant.
Dans ce cas, on a alors :
et donc d'après le lemme 1, est de coût minimal. L'algorithme va alors
consister à partir d'une fonction potentielle quelconque à définir , à déterminer le
flot maximal sur . Si ce flot est saturant, l'algorithme est terminé : on a trouvé le flot
de coût minimal. Si ce n'est pas le cas, il faut changer de telle façon qu'au bout d'un
certain nombre d'itérations, le flot sur
devienne saturant.
Remarquons que la première opération, consistant à se donner une fonction potentielle
n'a rien de difficile. Par exemple, si tous les
sont positifs, ce qui est en général le cas
donnent une fonction potentielle possible. Ce n'est
certainement pas la meilleure, et on a intérêt à bien choisir le de départ (cf. ci-dessous
l'application numérique).
Plaçons nous donc dans le cas où on a une fonction potentielle , un graphe , sur
lequel on a déterminé le flot maximal
; mais ce flot n'est pas saturant. Comment
changer ?
Si le flot est maximal pour , c'est qu'à la fin de l'algorithme de Ford-Fulkerson, un
certain nombre de sommets sont marqués, dont , les autres étant non marqués, dont .
Appelons :
: ensemble des sommets origines marqués,
: ensemble des sommets origines non marqués,