Donc à un sommet où il y a flux nul, les équations
et celle de conservation sont vérifiées;
mais la dernière est conséquence des autres!
Basé sur l'id'ée d'une
chaîne augmentante:
une suite de changements possibles
dans une chaîne d'arcs dont le résultat
est de transférer quantité
de la source
à un autre sommet.
NB: l'augmentation dans une chaîne augmentante peut diminuer le flux dans certains arcs!
Facile de trouver des chaînes augmentantes dans un arbre enraciné à la source
Si on trouve une chaîne augmentante au puits, on peut
augmenter le flot actuel (initialisé à )
par le minimum des changements possibles sur les arcs
de la chaîne
Sinon on a trouvé un flot maximum.
Chaque itération (sauf la dernière) augmente le flot
Donc le nombre d'itérations est borné par le flot maximum trouvé
(
), donc par la somme des capacités des arcs sortant
de la source (ou entrant dans le puits)
Donc temps total raisonnable si les capacités sont petites
Un algorithme
pseudo-polynomial
Peut être pire que le simplexe quand les capacités sont élevées.
Il existe des algorithmes plus complexes qui évitent ce défaut en cherchant la bonne chaîne augmentante à chaque itération. ...
...?
Non. Il peut trouver un flot maximum qui n'est pas une solution de base du PL.
(Considérer un réseau ne possédant que deux chemins source
- de capacités
chacun et deux chemins
- puits
de capacité 2.)
Pour l'itération
, il construit un nouveau graphe qui
est une copie partielle de celui du réseau mais qui ne contient
que les arcs susceptible d'être inclus dans une chaîne
augmentante
de longueur
Il utilise ce graphe pour chercher une chaîne
augmentante
de longueur
(et termine cette itération s'il
n'y en a pas)
Après chaque augmentation, il découpe du graphe tout arc
dont le flux vient d'être réduit à nul ou augmenté
à sa capacité
(et aussi tout autre arc qui n'est plus utile pour construire
des chaînes augmentantes).
A chaque itération construire un graphe
qui dépend du
flot actuel
et le graphe du réseau
: si
a un arc
avec coût
,
On cherche un chemin de la source au puits avec une valeur minimum
s'il existe on augment le flot selon la chaîne augmentante
correspondant
sinon l'algorithme termine.
Cette recherche est effectuée par un algorithme bien connu de recherche du plus court chemin entre deux sommets (seul complication ici, arcs de ``distance'' négative mais c'est pas grave)
La raison pour laquelle cet algorithme réussit est plus
compliquée,
en particulier, si on commencait d'un flot aléatoire,
il ne serait pas garanti qu'on arrive á un flot optimal;
mais, en commençant au flot nul, oui.