Énoncé et initialisation
Petit exemple numérique
La représentation graphique ci-dessus représente un réseau à travers lequel il faut écouler un flot maximum.
Le flot entre par le point 0 (la source) et sort par le point 7 (le puits).
La quantité sur les arcs représentent le flot maximal que l'on peut faire passer sur l'arc.
Les flots sont tous positifs ou nuls.
Les flots sont conservatifs : la somme des flots qui entrent dans un point est toujours égal à la somme des flots qui sortent de ce point.
Le flot maximal entre par la source et sort par le puits.
Initialisation de l'algorithme et structures de données utilisées
On utilise une file : les nouveaux points sont placés en queue de la file, alors que c'est toujours la tête de la liste que l'on supprime.
Une file correspond à la règle de priorité : premier arrivé, premier servi.
Ici la file est initialisée avec la source (le point 0).
Le point 0 est colorié en vert pâle, car c'est un point atteint par une augmentation potentielle du flot (en provenance de l'extérieur) mais dont on n'a pas encore examiné toutes les possibilités de propagation du flot au delà : on dit que le point 0 est marqué, mais non examiné.
Dans le tableau Delta, on range la quantité la plus grande possible que l'on peut acheminer par un chemin depuis la source.
La quantité qui peut atteindre la source est a priori illimitée.
On a néanmoins un majorant du flot max qui peut servir de valeur maximale à la place de +∞ et qui est la plus petite somme de flux qui sort de la source ou qui entre dans le puits (sur l'exemple, on aurait pu remplacer +∞ par 5).
Si Delta(i) est égal à 0 (ici barré), cela signifie qu'il n'est pas encore atteint par une augmentation potentielle du flot et donc non marqué.
Dans le tableau Origine, si le point est marqué, on indique le prédécesseur de ce point dans le chemin acheminant l'augmentation du flot depuis la source.
A l'initialisation, le seul point marqué est le point 0 avec Delta(0)=+∞ et Origine(0)="##" (qui signifie ici que l'on atteint le point 0 en venant de l'extérieur du réseau).
