Problèmes de flots
219
ne peut alors augmenter indéfiniment sans que le flot Ø n'augmente à son tour,
puisque Ø n'étant pas saturant, certains arcs
sont non saturés : au bout d'un certain
temps, on pourra marquer et augmenter le flot.
Récapitulons l'algorithme :
a) On se donne une fonction potentiel . (ensemble de et tels que
.
b) On détermine le graphe partiel
(obtenu en supprimant les arcs
tels que
c) On calcule le flot maximal sur .
Si ce flot sature les sommets origines et les sommets destination, ce flot est le flot de
coût minimal. L'algorithme s'arrête.
d) Si le flot maximal sur
n'est pas saturant on change , en augmentant d'une même
quantité les
des sommets origines marqués et diminuant les
des sommets
destinations marqués de façon à créer un nouvel arc sur . On retourne en c).
Pour cela on opère de la manière suivante :
i) On détermine les ensembles X 1 , X 2 , Y 1 , Y 2
X 1 : ensemble des sommets origines marqués
X 2 : ensemble des sommets origines non marqués
Y 1 : ensemble des sommets destinations marqués
Y 2 : ensemble des sommets destinations non marqués
ii) On calcule la quantité = Min [c ij – ( i + i )] = ij
i/ x i X 1, j/ y j Y 2
iii) On effectue sur les modifications suivantes :
’ i = i + pour x i X 1
’ i = i pour x i X 2
’i = i - pour y j Y 1
’ j = j pour yj Y 2
On revient à l’étape b)