Voir la source de Algorithme de Ford-Fulkerson

{{ébauche|informatique théorique}}{{À sourcer|date=mai 2021}}
{{Voir paronyme|Algorithme de Bellman-Ford}}
[[Fichier:FordFulkerson.gif|cadre|Exemple d'exécution de l'algorithme de Ford-Fulkerson. L'animation affiche le graphe résiduel correspondant à chaque itération.]]

En [[informatique]], l''''algorithme de Ford-Fulkerson''' est un algorithme pour le [[problème de flot maximum]], un problème d'optimisation classique dans le domaine de la [[recherche opérationnelle]]. Il est dû à [[Lester Randolph Ford junior]] et [[Delbert Ray Fulkerson|D. R. Fulkerson]]<ref>{{Article |langue=en |prénom1=L. R. |nom1=Ford |prénom2=D. R. |nom2=Fulkerson |titre=Maximal Flow Through a Network |périodique=Canadian Journal of Mathematics |volume=8 |date=1956/ed |issn=0008-414X |issn2=1496-4279 |doi=10.4153/CJM-1956-045-5 |lire en ligne=https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maximal-flow-through-a-network/5D6E55D3B06C4F7B1043BC1D82D40764 |consulté le=2021-05-29 |pages=399–404 }}</ref> et c'est une variante de l'[[algorithme de Busacker et Gowen]].

== Problème du flot maximum ==
{{Article détaillé|Problème de flot maximum}}

=== Définition du problème ===

Ce problème d'optimisation peut être représenté par un [[Théorie des graphes|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 [[Transport de marchandises|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 un stock initial de marchandises (Paris : 100 ; Lyon : 80 ; Marseille : 150). De même, chaque pays d'arrivée a une demande maximale pour les importations (Pologne : 120 ; Suède : 140 ; Grèce : 50).

L'algorithme de Ford-Fulkerson va permettre d'optimiser ces flux à l'aide d'un outil de [[Modèle mathématique|modélisation mathématique]]. La structure sous-jacente est représentée par un [[Théorie des graphes|graphe]] orienté dont le [[Sommet (théorie des graphes)|sommet]] de gauche symbolise le stock initial. Trois arcs en partent, chacun menant à un sommet représentant un centre de fret. Le sommet final symbolise la fin de la livraison, auquel mènent trois arcs venant de sommets représentant une destination de livraison.

Dans l'exemple présent, la [[matrice d'adjacence]] porte donc dans sa première ligne les valeurs desdits 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. Entre les sommets « centre de fret » et les sommets « destination » peuvent se trouver des sommets et des arcs intermédiaires, les capacités de ces arcs correspondant au fret maximal d'un point à l'autre.
<syntaxhighlight lang="text">
             Paris                        Pologne
           /       \                     /       \
    100 ---         -------  ...  -------         ---- 120
       /   80               Nœuds               140   \
Départ ------- Lyon ------ intermé- ---- Suède -------- Fin
       \                   diaires                    /
    150 ---         -------  ...  -------         ---- 50
           \       /                     \       /
           Marseille                       Grèce
</syntaxhighlight>
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.

=== Formalisation ===
==== Réseau ====
Soit un réseau <math>G = (S, A, c, s, t)</math> avec :
*<math>(S, A)</math> un graphe orienté irréflexif ;
*une capacité <math>c : A \rightarrow \mathbb{N}^\star</math> avec pour convention : si l'arc <math>(u, v)</math> n'existe pas, <math>c(u, v) = 0</math> ;
*un sommet source {{mvar|s}} sans arcs entrants ;
*un sommet puits {{mvar|t}} sans arcs sortants.

On suppose qu'il n'y a pas d'arcs anti-parallèles, c'est-à-dire que l'existence d'un arc <math>(u, v)</math> exclut l'existence d'un arc <math>(v, u)</math>.

==== Flot ====
Le [[Réseau de flot|flot d'un réseau]] est une fonction <math>f : S^2 \rightarrow \mathbb{R}^+</math> qui vérifie :
*pour tous sommets <math>(u, v) \in S \times S</math>, on a <math>0 \le f(u,v) \le c(u,v)</math> ;
*pour tout sommet <math>u \in S</math> tel que <math>u \neq s</math> et <math>u \neq t</math> : <math>\sum_{v \in S} f(v, u) = \sum_{w \in S} f(u, w)</math> (le flot entrant est égal au flot sortant : propriété de conservation).

La valeur d'un flot {{Mvar|f}} est <math>|f| = \sum_{v \in S} f(s, v)</math>.

== 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 {{mvar|G}} et de {{mvar|f}} qui indique les modifications possibles (ajout ou annulation) : c'est un graphe pondéré <math>R_f = (S, A_f, r_f)</math> où on a 

<center><math>r_f(u, v) = \left\{\begin{array}[t]{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.</math></center>

et <math>A_f = \{(u, v) \in S \times S | r_{f}(u, v) > 0\}</math>.

=== Pseudo-code ===

   '''Entrée''' Un réseau <math>G = (S, A, c, s, t)</math>
   '''Sortie''' Un flot maximal {{mvar|f}}
   '''Fonction''' Ford_Fulkerson(<math>G</math>)
      <math>f \leftarrow </math> flot nul
      '''Tant que''' il y a un chemin simple <math>\gamma</math> de {{mvar|s}} à {{mvar|t}} dans le graphe résiduel <math>R_f</math> :
         <math>\Delta = \min\{r_f(u,v) : (u,v) \in \gamma\}</math>
         '''Pour''' toute arête <math>(u,v) \in \gamma</math> :
            '''Si''' <math>(u,v) \in A</math> :
               <math>f(u,v) := f(u,v) + \Delta</math>
            '''Sinon''' :
               <math>f(v,u) := f(v,u) - \Delta</math>
      '''Renvoyer''' {{mvar|f}}

L'algorithme ne précise pas comment trouver chaque chemin <math>\gamma</math>. L'[[algorithme d'Edmonds-Karp]], spécialisation de l'algorithme de Ford-Fulkerson, propose de faire un [[parcours en largeur]].

Chaque chemin trouvé est garanti d’augmenter la valeur du flot, car il commence forcément par un arc sortant du sommet source et finit par un arc entrant dans le sommet puits.

=== Exemple d'exécution ===
{| class="wikitable"
| rowspan="3" | On considère le réseau de flot <math>G = (S,A,c,s,t)</math>, consistant du graphe <math>(S,A)</math> à quatre sommets <math>S = \{s,t,u,v\}</math> et cinq arêtes <math>A = \{(s,u), (u,t), (s,v), (v,t), (u,v)\}</math>, de la source <math> s \in S</math>, du puits <math>t \in S</math> et de la fonction de capacité <math>c\colon A \to\mathbb{R}_{\geq 0}</math>.

On commence avec le flot vide <math>f</math> qui attribue la valeur <math>0</math> à chaque arête. Initialement, le graphe résiduel <math>G_f</math>et les capacités résiduelles <math>r_f</math> correspondent alors exactement au réseau <math>G</math> avec les capacités <math>c</math>.
| style="min-width: 10em;" | Graphe <math>G</math> (avec capacité <math>c</math>)
| [[File:Fordfulk-residual-0.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>c(e)</math>
|-
| <math>(s,u)</math> || 4
|-
| <math>(u,t)</math> || 1
|-
| <math>(s,v)</math> || 2
|-
| <math>(v,t)</math> || 6
|-
| <math>(u,v)</math> || 3

|}
|-
| Flot <math>f</math>
| [[File:Fordfulk-flow-0.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>f(e)</math>
|-
| <math>(s,u)</math> || 0
|-
| <math>(u,t)</math> || 0
|-
| <math>(s,v)</math> || 0
|-
| <math>(v,t)</math> || 0
|-
| <math>(u,v)</math> || 0
|}
|-
| Graphe résiduel <math>G_f</math> (avec capacité résiduelle <math>r_f</math>)
| [[File:Fordfulk-residual-0.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>r_f(e)</math>
| <math>r_f(\overleftarrow{e})</math>
|-
| <math>(s,u)</math> || 4 || 0
|-
| <math>(u,t)</math> || 1 || 0
|-
| <math>(s,v)</math> || 2 || 0
|-
| <math>(v,t)</math> || 6 || 0
|-
| <math>(u,v)</math> || 3 || 0
|}

|-
| rowspan="3" | Supposons que l'algorithme choisisse d'abord le chemin <math>\gamma = \left((s,u),(u,v),(v,t)\right)</math> (bleu). Le long de ce chemin, on peut augmenter le débit au maximum de <math>3</math> puisque l'arête <math>(u,v)</math> est limitante (<math>r_f((u,v)) = 3</math>). Il en résulte un nouveau flot (qu'on appellera toujours <math>f</math>) avec <math>f((s,u)) = f((u,v)) = f((v,t)) = 3</math>.

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

Les trois arêtes <math>(s,u), (u,v), (v,t)</math> 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 <math>(t,v), (v,u), (u,s)</math> (en rouge) dans le graphe résiduel marquent alors le fait que l'on pourra toujours diminuer le flot sur ces arêtes.
| Chemin améliorant <math>\gamma</math> (avec capacités résiduelles <math>r_f</math>)
| [[File:Fordfulk-path-1.svg]]
|-
| Flot <math>f</math>
| [[File:Fordfulk-flow-1.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>f(e)</math>
|-
| <math>(s,u)</math> || 3
|-
| <math>(u,t)</math> || 0
|-
| <math>(s,v)</math> || 0
|-
| <math>(v,t)</math> || 3
|-
| <math>(u,v)</math> || 3
|}
|-
| Graphe résiduel <math>G_f</math> résultant (avec les nouvelles capacités résiduelles <math>r_f</math>)
| [[File:Fordfulk-residual-1.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>r_f(e)</math>
| <math>r_f(\overleftarrow{e})</math>
|-
| <math>(s,u)</math> || 1 || 3
|-
| <math>(u,t)</math> || 1 || 0
|-
| <math>(s,v)</math> || 2 || 0
|-
| <math>(v,t)</math> || 3 || 3
|-
| <math>(u,v)</math> || 0 || 3
|}
|-
| rowspan="3" | Supposons que l'algorithme sélectionne le chemin améliorant <math>\gamma = ((s,v),(v,u),(u,t))</math>. L'augmentation maximale du débit est limitée par la capacité résiduelle <math>r_f((u,t)) = c((u,t)) - f((u,t)) = 1 - 0 = 1</math>. Pour la première fois, on passe par un arête arrière (<math>(v,u)</math>). 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.
| Chemin améliorant <math>\gamma</math> (avec capacités résiduelles <math>r_f</math>)
| [[File:Fordfulk-path-2.svg]]
|-
| Flot <math>f</math>
| [[File:Fordfulk-flow-2.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>f(e)</math>
|-
| <math>(s,u)</math> || 3
|-
| <math>(u,t)</math> || 1
|-
| <math>(s,v)</math> || 1
|-
| <math>(v,t)</math> || 3
|-
| <math>(u,v)</math> || 2
|}
|-
| Graphe résiduel <math>G_f</math> résultant (avec les nouvelles capacités résiduelles <math>r_f</math>)
| [[File:Fordfulk-residual-2.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>r_f(e)</math>
| <math>r_f(\overleftarrow{e})</math>
|-
| <math>(s,u)</math> || 1 || 3
|-
| <math>(u,t)</math> || 0 || 1
|-
| <math>(s,v)</math> || 1 || 1
|-
| <math>(v,t)</math> || 3 || 3
|-
| <math>(u,v)</math> || 1 || 2
|}

|-
| rowspan="3" | Supposons que l'algorithme choisisse à nouveau le chemin <math>\gamma = \left((s,u),(u,v),(v,t)\right)</math>. 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.
| Chemin améliorant <math>\gamma</math> (avec capacités résiduelles <math>r_f</math>)
| [[File:Fordfulk-path-3.svg]]
|-
| Flot <math>f</math>
| [[File:Fordfulk-flow-3.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>f(e)</math>
|-
| <math>(s,u)</math>
| 4
|-
| <math>(u,t)</math>
| 1
|-
| <math>(s,v)</math>
| 1
|-
| <math>(v,t)</math>
| 4
|-
| <math>(u,v)</math>
| 3
|}
|-
| Graphe résiduel <math>G_f</math> résultant (avec les nouvelles capacités résiduelles <math>r_f</math>)
| [[File:Fordfulk-residual-3.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>r_f(e)</math>
| <math>r_f(\overleftarrow{e})</math>
|-
| <math>(s,u)</math> || 0 || 4
|-
| <math>(u,t)</math> || 0 || 1
|-
| <math>(s,v)</math> || 1 || 1
|-
| <math>(v,t)</math> || 2 || 4
|-
| <math>(u,v)</math> || 0 || 3
|}

|-
| rowspan="3" | Ici, seul le chemin <math>\gamma = ((s,v),(v,t))</math> est possible. Cela augmente alors le débit de 1. Le flot a alors une valeur de <math>f((s,u)) + f((s,v)) = 6</math>. 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 (théorie des graphes)|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.
| Chemin améliorant <math>\gamma</math> (avec capacités résiduelles <math>r_f</math>)
| [[File:Fordfulk-path-4.svg]]
|-
| Flot maximal <math>f</math>
| [[File:Fordfulk-flow-4.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>f(e)</math>
|-
| <math>(s,u)</math> || 4
|-
| <math>(u,t)</math> || 1
|-
| <math>(s,v)</math> || 2
|-
| <math>(v,t)</math> || 5
|-
| <math>(u,v)</math> || 3
|}
|-
| Graphe résiduel <math>G_f</math> résultant (avec les nouvelles capacités résiduelles <math>r_f</math>)
| [[File:Fordfulk-residual-4.svg]]
|
{| class="wikitable"
| <math>e \in A</math>
| <math>r_f(e)</math>
| <math>r_f(\overleftarrow{e})</math>
|-
| <math>(s,u)</math> || 0 || 4
|-
| <math>(u,t)</math> || 0 || 1
|-
| <math>(s,v)</math> || 0 || 2
|-
| <math>(v,t)</math> || 1 || 5
|-
| <math>(u,v)</math> || 0 || 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érence nécessaire|date=November 2020}} Lorsque les capacités sont des entiers, le temps d'exécution de l'algorithme de Ford-Fulkerson est borné par <math>O(A f)</math> (voir les [[Comparaison asymptotique|notations de Landau]]), où <math>A</math> est le nombre d'arêtes dans le réseau de flot et <math>f</math> est la valeur du flot maximal. En effet, chaque chemin augmentant peut être trouvé en <math>O(A)</math> et augmente le débit d'une quantité entière d'au moins <math>1</math> avec <math>f</math> 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 <math>O(SA^2)</math>.

=== Terminaison ===

Si les capacités des arêtes sont des entiers, l'algorithme se termine. En effet, la suite des flots calculés est à valeurs entières. strictement croissante, et majorée par la valeur du flot maximal. Elle ne peut donc pas être infinie, et l'algorithme se termine.

== Exemple pour lequel l'algorithme ne termine pas ==

[[File:Ford-Fulkerson forever.svg|right]]

On s'intéresse au graphe suivant, qui a pour sommet source <math>s</math>, pour sommet puits <math>t</math>. Les arêtes <math>e_1</math>, <math>e_2</math> et <math>e_3</math> ont pour capacités respectives <math>1</math>, <math>r=(\sqrt{5}-1)/2</math> et <math>1</math>. La capacité des autres arêtes est fixée à <math>10</math>. On a choisi la constante <math>r</math> de sorte que <math>r^2 = 1 - r</math>. On considère l'exécution de l'algorithme choisissant les chemins suivants, où on note <math>p_1 = \{ s, v_4, v_3, v_2, v_1, t \}</math>, <math>p_2 = \{ s, v_2, v_3, v_4, t \}</math> et <math>p_3 = \{ s, v_1, v_2, v_3, t \}</math>.

{| class="wikitable" style="text-align: center"
! rowspan=2 | Étape !! rowspan=2 | Chemin choisi !! rowspan=2 | Augmentation du flot !! colspan=3 | Capacité résiduelle
|-
! <math>e_1</math> !! <math>e_2</math> !! <math>e_3</math>
|-
| 0 || || || <math>r^0=1</math> || <math>r</math> || <math>1</math>
|-
| 1 || <math>\{ s, v_2, v_3, t \}</math> || <math>1</math> || <math>r^0</math> || <math>r^1</math> || <math>0</math>
|-
| 2 || <math>p_1</math> || <math>r^1</math> || <math>r^2</math> || <math>0</math> || <math>r^1</math>
|-
| 3 || <math>p_2</math> || <math>r^1</math> || <math>r^2</math> || <math>r^1</math> || <math>0</math>
|-
| 4 || <math>p_1</math> || <math>r^2</math> || <math>0</math> || <math>r^3</math> || <math>r^2</math>
|-
| 5 || <math>p_3</math> || <math>r^2</math> || <math>r^2</math> || <math>r^3</math> || <math>0</math>
|}

On remarque qu'après les étapes 1 et 5, les capacités résiduelles des arêtes <math>e_1</math>, <math>e_2</math> et <math>e_3</math> sont respectivement de la forme <math>r^n</math>, <math>r^{n+1}</math> et <math>0</math> et le flot ajouté est <math>r^n</math> où <math>n \in \mathbb{N}</math>. Ainsi, par récurrence on pourra toujours répéter la boucle de chemins <math>p_1</math>, <math>p_2</math>, <math>p_1</math> et <math>p_3</math> tout en ajoutant un flot strictement positif car les capacités résiduelles resteront toujours de la forme <math>r^n</math>, <math>r^{n+1}</math> et <math>0</math> à la fin de l'exécution sur les chemins. L'algorithme ne termine donc pas sur cette entrée. Le fait que l'on ait une capacité irrationnelle par rapport aux autres capacités entières est cruciale car elle permet d'avoir une suite de taille de flot infinie strictement croissante et majorée<ref>{{article| titre = The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate | prénom = Uri | nom = Zwick|lien auteur=Uri Zwick | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 148 | numéro = 1 | date = 21 August 1995 | pages = 165–170 | doi = 10.1016/0304-3975(95)00022-O| accès doi = libre }}</ref>.
== Notes et références ==
<references />

== 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 ===
* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/MaxflowApp.shtml?demo2 Applets Java de démonstration]
* Un article de vulgarisation : {{lien web |url=http://images.math.cnrs.fr/Au-feu-les-pompiers.html |titre=Au feu les pompiers |site=[[Images des Maths]] |consulté le=17 janvier 2023 |auteur=Xavier Caruso et Lionel Fourquaux}}

=== Bibliographie ===
{{Autres projets|commons=Category:Ford-Fulkerson's algorithm}}
* ''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|Rand Corporation]], Santa Monica, {{date-|décembre 1955}}.
*  {{article
 | titre = Maximal flow through a network
 | nom1 = Ford | prénom1 = Lester R.
 | nom2 = Fulkerson | prénom2 = Delbert R.
 | périodique = Canadian journal of Mathematics
 | volume = 8
 | numéro = 3
 | passage = 399-404
 | année = 1956}}
* ''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.) [[Éditions Dunod|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.
* {{ouvrage
 | nom1 =  Ford 
 | prénom1 = Lester Randolph 
 | lien auteur1 = Lester Randolph Ford
 | nom2 = Fulkerson
 | prénom2 = Delbert Ray 
 | lien auteur2 = Delbert Ray Fulkerson
 | année = 1962
 | titre = Flows in Networks
 | éditeur = Princeton University Press
 | lieu = Princeton, NJ
}}
* {{ouvrage
 | nom1 =  Ajuha 
 | prénom1 = Ravindra K.
 | nom2 = Magnanti
 | prénom2 = Thomas L.
 | nom3 = Orlin
 | prénom3 = James B.
 | année = 1993
 | titre = Network flows - theory, algorithms and applications
 | éditeur = Prentice Hall
}}
* {{ouvrage
 | nom1 =  Cormen 
 | prénom1 = Thomas H.
 | nom2 = Leiserson
 | prénom2 = Charles E.
 | nom3 = Rivest
 | prénom3 = Ronald L.
 | nom4 = Stein
 | prénom4 = Clifford
 | année = 2009
 | titre = Introduction to algorithms
 | éditeur = MIT Press
}}
* {{ouvrage
 | nom1 =  Kleinberg 
 | prénom1 = Jon
 | nom2 = Tardos
 | prénom2 = Eva
 | année = 2006
 | titre = Algorithms design
 | éditeur = Pearson Education India
}}

{{Palette|Algorithmes sur les graphes}}
{{Portail|mathématiques|informatique théorique}}

[[Catégorie:Algorithme d'optimisation|Ford-Fulkerson]]
[[Catégorie:Algorithme de la théorie des graphes|Ford-Fulkerson]]
[[Catégorie:Recherche opérationnelle]]
[[Catégorie:Réseau de flot]]