Description de l'algorithme de Ford et Fulkerson
Tous les éléments nécessaires ont été introduits à la section précédente.
Cette section est plus destinée aux personnes qui s'intéressent à l'implémentation informatique de l'algorithme de Ford et Fulkerson.
La section suivante vous permet de comprendre son déroulement détaillée sur un tout petit exemple.
Hypothèse
On suppose que le graphe est connexe et comporte une seule source et un seul puits.
Description globale de l'algorithme de Ford et Fulkerson
Mettre à 0 les flots F(x,y) de tous les arcs (x,y) du graphe ;
Tant que il existe une chaîne améliorante faire
Améliorer le flot sur la chaîne trouvée ;
Fin tant que
Mettre en évidence la coupe au delà des chaînes améliorantes construites.
RECHERCHE D'UNE CHAÎNE AMÉLIORANTE
Nous nous plaçons à une itération quelconque de l'algorithme où les flots F(x,y) sont positifs ou nuls.
Nous cherchons à construire une chaîne améliorante en utilisant un algorithme de cheminement utilisant des marquages et une file d'attente où on met en queue les nouveaux points atteints par des arcs "avant" non saturés ou par des arcs "arriere" à flux non nul et où on supprime la tête de la file lorsque l'on a examiné tous les arcs "avant" et/ou "arrière" de ce point.
Remarque :
Comme nous n'avons besoin que d'une seule file pour implanter cet algorithme, nous avons simplifié les notations en n'utilisant pas de paramétrage pour désigner le nom de la file sur laquelle travaillent les fonctions utilisées. Les quatre lettres FILE mettent en évidence le fait que l'on définit des fonctions sur cette unique file.
Remarque :
Nous avons numéroté la source 0.
Nous désignons par t le puits, en général il correspond au point de plus grand numéro n-1.
Notations
MARQUE(i) = 0 si le point n'a pas encore été atteint par une chaîne améliorante en construction et 1 dans le cas contraire.
DELTA(i) = 0 pour les points non marqués, + ∞ pour la source et la plus grande valeur Δ que l'on peut utiliser pour modifier les flux de manière conservative sur la chaîne en construction qui a pour origine la source et pour extrémité le point i.
ORIGINE(i) = - ∞ pour les points non marqués, + ∞ pour la source et + ou - le numéro du point (tête de la file) j qui a permis de l'atteindre i :
+ j si i a été atteint par un arc "avant" et - j si i a été atteint par un arc "arrière".
FILE : la structure de données de type file qui contient les points marqués dont on n'a pas encore examiné la poursuite potentielle d'une chaîne améliorante en examinant ses prédécesseurs et ses successeurs.
La fonction VIDE_FILE vide la file.
La fonction AJOUTER_FILE(k) ajoute l'élément k à la queue de la file.
La fonction TETE_FILE donne le contenu positif de la tête de la file et -1 si la file est vide.
La fonction OTE_TETE_FILE enlève la tête de la file.
La fonction NBSUCC(i) donne le nombre de successeurs du point i et SUCC(i,k) donne le numéro du kème successeur de i.
La fonction NBPRED(i) donne le nombre de prédécesseurs du point i et PRED(i,k) donne le numéro du kème prédécesseur de i.
Initialisation de la recherche d'une chaîne améliorante
// EFFACEMENT DE TOUTES MARQUES ANTERIEURES
POUR TOUT i FAIRE
MARQUE(i)=0;
DELTA(i)=0;
ORIGINE(i)= - ∞;
FIN POUR TOUT
// MARQUER LA SOURCE ET REINIALISER LA FILE
MARQUE(0)=1;
DELTA(0)=+ ∞;
ORIGINE(0)=+ ∞;
VIDE_FILE;
AJOUTER_FILE(0);
NBSUCC_TETE=NBSUCC(0);
NBPRED_TETE=0;
Remarque
Dans l'algorithme suivant, on a numéroté les SI, ALORS, SINON et FIN SI de manière à rendre l'algorithme plus lisible car les indentations ne suffisaient pas.
Construction de la chaîne améliorante
TANT QUE TETE_FILE > 0 ET MARQUE(t) = 0 FAIRE
SI_1 NBSUCC_TETE > 0
ALORS_1
// On n'a pas encore examiné tous les successeurs de la tête de la file
A_CONSIDERER = SUCC(TETE_FILE, NBSUCC_TETE);
NBSUCC_TETE = NBSUCC_TETE - 1;
SI_2 MARQUE(A_CONSIDERER) = 0 ET
F(TETE_FILE, A_CONSIDERER) < C(TETE_FILE, A_CONSIDERER)
ALORS_2
// Un successeur de la tête de la file est non marqué
// et peut être atteint par une augmentation de flot par un arc "avant"
MARQUE(A_CONSIDERER)=1;
DELTA(A_CONSIDERER)= MINIMUM(DELTA(TETE_FILE),
C(TETE_FILE, A_CONSIDERER) - F(TETE_FILE, A_CONSIDERER))
ORIGINE(A_CONSIDERER)=TETE_FILE;
AJOUTER_FILE(A_CONSIDERER);
FIN_SI_2 // de marquage d'un point successeur
SINON_1
SI_3 NBPRED_TETE > 0
ALORS_3
// On n'a pas encore examiné tous les prédecesseurs de la tête de la file
A_CONSIDERER = PRED(TETE_FILE, NBPRED_TETE);
NBPRED_TETE = NBPRED_TETE - 1;
SI_4 MARQUE(A_CONSIDERER) = 0 ET F(A_CONSIDERER, TETE_FILE) > 0
ALORS_4
// Un prédécesseur de la tête de la file est non marqué
// et peut être atteint par une augmentation de flot par un arc "arrière"
MARQUE(A_CONSIDERER)=1;
DELTA(A_CONSIDERER)=MINIMUM(DELTA(TETE_FILE), F(A_CONSIDERER, TETE_FILE))
ORIGINE(A_CONSIDERER)= - TETE_FILE;
AJOUTER_FILE(A_CONSIDERER);
FIN SI_4 // de marquage d'un point prédécesseur
SINON_3
// On a examiné tous les successeurs et prédécesseurs
// de la tête de la file.
// Il faut donc ôter la tête de la file
// et passer au point suivant dans la file.
OTE_TETE_FILE;
SI_5 TETE_FILE > 0
ALORS_5
// La file n'est pas vide
// Il faut initialiser NBPRED_TETE et NBSUCC_TETE
// pour cette nouvelle tête de file
NBSUCC_TETE=NBSUCC(TETE_FILE);
NBPRED_TETE=NBPRED(TETE_FILE);
FINSI_5 // de réinitialisation de la tête de file
FINSI_3 // de fin d'examen d'une tête de file
FSI_1 // on a terminé d'examiner une fois la tête de la file
FIN TANT QUE
Remarque :
L'algorithme de construction de la chaîne améliorante s'arrête pour deux raisons.
Soit parce qu'on a marqué le puits t et dans ce cas il faut améliorer le flot sur la chaîne trouvée.
Soit parce que la file s'est vidée sans que l'on arrive à marquer le puits et dans ce cas, il n'existe pas de chaîne améliorante, on est à l'optimum pour le flot et on peut trouver une coupe minimale en utilisant les marques.
Amélioration du flot sur la chaîne améliorante trouvée
MODIF = DELTA(t);
X2=t ;
X1=ORIGINE(t);
F(X1,X2)=F(X1,X2) + MODIF;
TANT QUE X1 n'est pas la source FAIRE
X2=X1;
X1=ORIGINE(X2);
SI X1 > 0
ALORS
// (X1, X2) est un arc "avant"
F(X1,X2)=F(X1,X2) + MODIF;
SINON
// (X2, -X1) est un arc "arrière"
X1=-X1;
F(X2,X1)=F(X2,X1) - MODIF;
FIN SI
FIN TANT QUE
Mise en évidence d'une coupe minimale
Lorsque l'algorithme s'arrête car on n'a pas trouvé de chaîne améliorante, les marques n'ont pas été effacées et on trouve la coupe en considérant tous les arcs ayant pour origine un point marqué et pour extrémité un point non marqué.
