Algorithme de Ford-Fulkerson

En informatique, l'algorithme de Ford-Fulkerson est un algorithme pour le problème du flot maximum, un problème d'optimisation classique dans le domaine de la recherche opérationnelle. Il est dû à Lester Randolph Ford junior et D. R. Fulkerson[1] et c'est une variante de l'algorithme de Busacker et Gowen.

Exemple d'exécution de l'algorithme de Fold-Fulkerson

Problème du flot maximum

Définition du problème

Ce problème d'optimisation peut être représenté par un graphe comportant une entrée (à gauche) et une sortie (à droite). Le flot représente la circulation de l'entrée vers la sortie d'où l'utilisation de cet algorithme dans les problèmes de réseaux. Les applications sont multiples : problèmes informatiques, routiers, ferroviaires, etc. Il s'applique également à tous les autres problèmes de transferts comme les importations/exportations, les flux migratoires, démographiques mais aussi sur des flux purement numériques tels que les transferts financiers. Pour les données de très grande taille, il existe plusieurs algorithmes plus performants pour résoudre le problème de flot maximum.

Exemple d'application

Une société de fret dispose de trois centres : un à Paris, le deuxième à Lyon, le troisième à Marseille.
Trois destinations sont possibles : la Pologne, la Suède, la Grèce.

Chacun des centres de fret a une capacité maximale de transport ainsi qu'un stock initial de marchandises. De même, chaque pays d'arrivée a une demande maximale pour les importations.

L'algorithme de Ford-Fulkerson va permettre d'optimiser ces flux à l'aide d'un outil de modélisation mathématique. La structure sous-jacente est représentée par un graphe orienté dont le sommet de gauche symbolise le stock initial. Celui-ci est relié à chacun des premiers arcs ou arêtes.

Dans l'exemple présent, la matrice d'adjacence porte donc dans sa première colonne les valeurs des dits stocks. Inversement, à l'extrémité de la chaîne, la matrice associée comprendra dans sa dernière colonne les demandes respectives des pays cités. Les sommets centraux comprendront les différentes combinaisons de fret maximal d'un point à l'autre.

Le problème peut être généralisé à une circulation dans un réseau (véhicules, fluides, monnaie, etc.), les grandeurs mathématiques remplaçant indistinctement les faits réels qu'elles sont censées représenter.

Réseau

Soit un réseau $G=(S,A,c,s,t)$ avec :

$(S,A)$ un graphe orienté irréflexif
une capacité $c:A\rightarrow \mathbb {N} ^{\star }$ avec pour convention: si l'arête $(u,v)$ n'existe pas, $c(u,v)=0$
un sommet source $s$ sans arcs entrants
un sommet puits $t$ sans arcs sortants

On suppose qu'il n'y a pas d'arcs anti-parallèles, c'est-à-dire qu'il n'y a pas d'arcs de $u$ vers $v$ et de $v$ vers $u$ .

Flot

Le flot d'un réseau est une fonction $f:S^{2}\rightarrow \mathbb {R} ^{+}$ qui vérifie :

pour tous sommets $(u,v)\in S\times S$ , on a $0\leq f(u,v)\leq c(u,v)$
pour tout sommet $u\in S$ tel que $u\neq s$ et $u\neq t$ : $\sum _{v\in S}f(v,u)=\sum _{w\in S}f(u,w)$ (le flot entrant est égal au flot sortant).

La valeur d'un flot f est $|f|=\sum _{v\in S}f(s,v)$ .

Algorithme

Il s'agit d'un algorithme itératif. À chaque itération, la solution courante est un flot qui satisfait les contraintes de capacité (c'est donc un flot réalisable) et l'algorithme essaie d'augmenter la valeur de ce flot. Cela peut nécessiter d'annuler les mauvais choix. Pour ce faire, on définit le graphe résiduel de G et de f qui indique les modifications possibles (ajout ou annulation): c'est un graphe pondéré $R_{f}=(S,A_{f},r_{f})$ où on a

r_{f}(u,v)=\left\{{\begin{array}{cl}c(u,v)-f(u,v)&\mathrm {si} \ (u,v)\in A&\mathrm {(ajout)} \\f(v,u)&\mathrm {si} \ (v,u)\in A&\mathrm {(annulation)} \\0&\mathrm {sinon} \ \end{array}}\right.

et $A_{f}=\{(u,v)\in S\times S|r_{f}(u,v)>0\}$ .

Pseudo-code

  Entrée  Un réseau  $G=(S,A,c,s,t)$ 
  Sortie Un flot maximal  $f$ 
  Fonction Ford_Fulkerson( $G$ )
      $f\leftarrow$  flot nul
     Tant que il y a un chemin simple  $\gamma$  de s à t dans le graphe résiduel  $R_{f}$  faire:
         $\Delta =\min\{r_{f}(u,v):(u,v)\in \gamma \}$ 
        pour toute arête  $(u,v)\in \gamma$ 
           si  $(u,v)\in A$  :
               $f(u,v):=f(u,v)+\Delta$ 
           sinon :
               $f(v,u):=f(v,u)-\Delta$ 
     renvoyer  $f$

Exemple d'exécution

Description

Graphe

G

(avec capacité

c

)

Flot

f

Graphe résiduel

G_{f}

(avec capacité résiduelle

r_{f}

)

On considère le réseau de flot

G=(S,A,c,s,t)

, consistant du graphe

(S,A)

à quatre sommets

S=\{s,t,u,v\}

et cinq arêtes

A=\{(s,u),(u,t),(s,v),(v,t),(u,v)\}

, de la source

s\in S

, du puits

t\in S

et de la fonction de capacité

c\colon A\to \mathbb {R} _{\geq 0}

.

On commence avec le flot vide $f$ qui attribue la valeur $0$ à chaque arête. Initialement, le graphe résiduel $G_{f}$ et les capacités résiduelles $r_{f}$ correspondent alors exactement au réseau $G$ avec les capacités $c$ .

$e\in S$	$c(e)$
(s,u)	4
(u,t)	1
(s,v)	2
(v,t)	6
(u,v)	3

$e\in S$	$f(e)$
(s,u)	0
(u,t)	0
(s,v)	0
(v,t)	0
(u,v)	0

$e\in S$	$r_{f}(e)$	$r_{f}({\overleftarrow {e}})$
(s,u)	4
(u,t)	1
(s,v)	2
(v,t)	6
(u,v)	3

Description

Chemin améliorant

\gamma

(avec capacités résiduelles

r_{f}

)

Flot

f

Graphe résiduel

G_{f}

résultant (avec les nouvelles capacités résiduelles

r_{f}

)

Supposons que l'algorithme choisisse d'abord le chemin

\gamma =\left((s,u),(u,v),(v,t)\right)

(bleu). Le long de ce chemin, on peut augmenter le débit au maximum de

3

puisque l'arête

(u,v)

est limitante (

r_{f}((u,v))=3

). Il en résulte un nouveau flot (qu'on appellera toujours

f

) avec

f((s,u))=f((u,v))=f((v,t))=3

.

L'arête $(s,u)$ a une capacité de $c((s,u))=4$ . Elle est utilisée dans le flot : $f((s,u))=3$ . Dans le graphe résiduel, sa capacité résiduelle sera donc $r_{f}((s,u))=c((s,u))-f((s,u))=1$ . De même $r_{f}((u,v))=c((u,v))-f((u,v))=3-3=0$ et $r_{f}((v,t))=c((v,t))-f((v,t))=6-3=3$ .

Les trois arêtes $(s,u),(u,v),(v,t)$ sont strictement positives dans le flot. Ces poids dans le flot ne sont peut être pas les plus optimaux. Les nouvelles arêtes arrières $(t,v),(v,u),(u,s)$ (en rouge) dans le graphe résiduel marquent alors le fait que l'on pourra toujours diminuer le flot sur ces arêtes.

$e\in S$	$f(e)$
(s,u)	3
(u,t)	0
(s,v)	0
(v,t)	3
(u,v)	3

$e\in S$	$r_{f}(e)$	$r_{f}({\overleftarrow {e}})$
(s,u)	1	3
(u,t)	1
(s,v)	2
(v,t)	3	3
(u,v)		3

Supposons que l'algorithme sélectionne le chemin améliorant

\gamma =((s,v),(v,u),(u,t))

. L'augmentation maximale du débit est limitée par la capacité résiduelle

r_{f}((u,t))=c((u,t))-f((u,t))=1-0=1

. Pour la première fois, on passe par un arête arrière (

(v,u)

). Alors que le flot f augmente de 1 le long des arêtes (s,v) et (u,t), il diminue de 1 le long de (u,v).

On peut remarquer que les capacités résiduelles des arêtes arrières sont toujours égales aux poids dans le flot.

$e\in S$	$f(e)$
(s,u)	3
(u,t)	1
(s,v)	1
(v,t)	3
(u,v)	2

$e\in S$	$r_{f}(e)$	$r_{f}({\overleftarrow {e}})$
su	1	3
(u,t)		1
(s,v)	1	1
(v,t)	3	3
(u,v)	1	2

Supposons que l'algorithme choisisse à nouveau le chemin

\gamma =\left((s,u),(u,v),(v,t)\right)

. Cette fois, le débit le long du chemin ne peut être augmenté que de 1. Cela correspond justement au montant par lequel on a diminué (u,v) à l'étape précédente. En effet, l'algorithme peut faire beaucoup de va-et-vient.

$e\in S$	$f(e)$
su	4
(u,t)	1
(s,v)	1
(v,t)	4
(u,v)	3

$e\in S$	$r_{f}(e)$	$r_{f}({\overleftarrow {e}})$
su		4
(u,t)		1
(s,v)	1	1
(v,t)	2	4
(u,v)		3

Ici, seul le chemin

\gamma =((s,v),(v,t))

est possible. Cela augmente alors le débit de 1. Le flot a alors une valeur de

f((s,u))+f((s,v))=6

. Les arêtes sortantes de la source sont pleinement utilisées donc ce flot est un flot maximal. La coupure au niveau de (s,u) et (s,v) est donc une coupe minimale. On respecte donc bien le Théorème flot-max/coupe-min qui affirme qu'un flot maximal a la même valeur qu'une coupe minimale.

L'algorithme se termine alors car aucun chemin de s à t n'existe dans le graphe résiduel obtenu. On a donc bien obtenu un flot maximal.

$e\in S$	$f(e)$
su	4
(u,t)	1
(s,v)	2
(v,t)	5
(u,v)	3

$e\in S$	$r_{f}(e)$	$r_{f}({\overleftarrow {e}})$
su		4
(u,t)		1
(s,v)		2
(v,t)	1	5
(u,v)		3

Propriétés de l'algorithme

Complexité

Le flot maximal est atteint quand plus aucun chemin améliorant ne peut être trouvé. Cependant, il n'y a aucune certitude que cette situation soit atteinte, mais la réponse sera correcte si l'algorithme se termine. Dans le cas où l'algorithme s'exécute indéfiniment, le flot peut même ne pas converger vers le flot maximum. Néanmoins, cette situation ne se produit qu'avec des valeurs de flot irrationnelles.^{[réf. nécessaire]} Lorsque les capacités sont des entiers, le temps d'exécution de l'algorithme de Ford-Fulkerson est borné par $O(Af)$ (voir les notations de Landau), où $A$ est le nombre d'arêtes dans le réseau de flot et $f$ est la valeur du flot maximal. En effet, chaque chemin augmentant peut être trouvé en $O(A)$ et augmente le débit d'une quantité entière d'au moins $1$ avec $f$ comme borne supérieure.

Une variante de l'algorithme de Ford-Fulkerson avec terminaison garantie et un temps d'exécution indépendant de la valeur de flot maximal est l' algorithme d'Edmonds-Karp, qui a une complexité temporelle en $O(SA^{2})$ .

Terminaison

Si les capacités des arêtes sont des entiers, l'algorithme se termine.

On peut le démontrer par l'absurde, en supposant que l'algorithme ne se termine pas. En considérant la suite des flots calculés, on distingue plusieurs propriétés :

La suite est strictement croissante
Elle est majorée par la valeur du flot maximal
Elle est à valeurs entières

Cette suite entière est infinie, majorée et strictement croissante, ce qui est absurde.

Notes et références

(en) L. R. Ford et D. R. Fulkerson, « Maximal Flow Through a Network », Canadian Journal of Mathematics, vol. 8,‎ 1956/ed, p. 399–404 (ISSN 0008-414X et 1496-4279, DOI 10.4153/CJM-1956-045-5, lire en ligne, consulté le 29 mai 2021)

Voir aussi

Article connexe

L'algorithme d'Edmonds-Karp est une spécialisation de l'algorithme de Ford-Fulkerson de résolution du problème de flot maximum dans un réseau.

Liens externes

Applets JavaScript de démonstration.
Un article de vulgarisation : Xavier Caruso et Lionel Fourquaux, « Au feu les pompiers », sur Images des Maths

Bibliographie

A simple algorithm for finding maximal network flows and an application to the Hitchock problem (FORD L.R., FULKERSON D.R), Rand Report Rand Corporation, Santa Monica, décembre 1955.
Lester R. Ford et Delbert R. Fulkerson, « Maximal flow through a network », Canadian journal of Mathematics, vol. 8, n^o 3,‎ 1956, p. 399-404
The transhipment problem (ORDEN A.), Management Science 2, 1956.
Sur la déficience d'un réseau infini (BERGE C.), Comptes rendus de l'Académie des Sciences 245, 1957.
Invitation à la recherche opérationnelle (KAUFMANN A., FAURE R.) Dunod Entreprise, 1979.
Contribution de la théorie des graphes à l'étude des problèmes d'ordonnancement (ROY B.) Congrès international de recherche opérationnelle, 1960.
Lester Randolph Ford et Delbert Ray Fulkerson, Flows in Networks, Princeton, NJ, Princeton University Press, 1962
Ravindra K. Ajuha, Thomas L. Magnanti et James B. Orlin, Network flows - theory, algorithms and applications, Prentice Hall, 1993
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to algorithms, MIT Press, 2009
Jon Kleinberg et Eva Tardos, Algorithms design, Pearson Education India, 2006

Portail des mathématiques
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) L. R. Ford et D. R. Fulkerson, « Maximal Flow Through a Network », Canadian Journal of Mathematics, vol. 8,‎ 1956/ed, p. 399–404 (ISSN 0008-414X et 1496-4279, DOI 10.4153/CJM-1956-045-5, lire en ligne, consulté le 29 mai 2021)