Le problème de flot maximum : explication de l’algorithme de Ford et Fulkerson

Lors de la première itération, on va chercher à augmenter le flux allant du noeud d'entrée au noeud de sortie. On teste pour cela différents noeuds (l'ordre dans lequel on les examine est l'ordre chronologique ou alphabétique des noeuds indiqué en T. Autrement dit, si T= {A, B, C } on examinera tout d'abord A puis B puis C.

Ensuite, à l'itération 2 : il faut refaire un nouveau schéma avec les augmentations de flux effectives trouvées à l'itération 1. Autrement dit, si on a trouvé une augmentation de 100 du flux de sortie, il faut augmenter de 100 le flux d'entrée quand bien même on aurait indiqué qu'il pouvait augmenter de 150, il s'agit là d'une augmentation théorique et on indique par conséquent '+100' sur notre schéma.