Algorithme d'Edmonds-Karp
# Algorithme d'Edmonds-Karp

En informatique et en théorie des graphes, l'algorithme d'Edmonds–Karp (ou algorithme d'Edmonds et Karp) est une spécialisation de l'algorithme de Ford-Fulkerson de résolution du problème de flot maximum dans un réseau, en temps O(V $E^2).$ Il est asymptotiquement plus lent que l'algorithme de poussage/reétiquetage qui utilise une heuristique basée sur une pile et qui est en temps $O(V^3),$ mais il est souvent plus rapide en pratique pour des graphes denses. L'algorithme a été publié d'abord par Yefim (Chaim) Dinic en 1970 puis et indépendamment par Jack Edmonds et Richard Karp en 1972. L'algorithme de Dinic contient un critère de sélection supplémentaire qui réduit le temps de calcul à $O(V^2$ E).

## Algorithme

L'algorithme est identique à l'algorithme de Ford-Fulkerson, à l'exception de l'ordre de recherche utilisé pour déterminer un chemin augmentant. Le chemin trouvé doit être un chemin le plus court (en nombre d'arcs) qui possède une capacité positive, dans le graphe résiduel. Un tel chemin peut être trouvé par un parcours en largeur dans le graphe résiduel, en supposant que les arcs ont tous une longueur unité.

Le temps d'exécution de O(V $E^2)$ s'obtient en constatant que chaque chemin augmentant peut être trouvé en temps O(E), qu'à chaque fois au moins un arc de E est saturé, que la distance de la source à un arc saturé par le chemin augmentant croît à chaque fois que l'arc est saturé, et que cette longueur est au plus V. Une autre propriété de cet algorithme est que la longueur du plus court chemin augmentant croît. Une démonstration de l'algorithme est donnée dans le livre Introduction à l'algorithmique de Cormen et al.

Sur les autres projets Wikimedia :

* Algorithme d'Edmonds-Karp (en anglais), sur Wikibooks

## Exemple

On part du réseau ci-dessous, à sept nœuds. La source est $A$, le puits est $G$. Les capacités sont indiquées sur les arcs.

Dans les couples $f/c$ d'étiquettes des arcs, $f$ est le flot courant, et $c$ est la capacité. La capacité résiduelle de $u$ vers $v$ est par définition

    $c_{f}(u,v)=c(u,v)-f(u,v)$,

c'est-à-dire la capacité totale, diminuée du flot déjà utilisé. Si le flot de $u$ vers $v$ est supérieur à la capacité, la capacité résiduelle est négative, et sa contribution est négative.

| capacité | chemin |
| - | - |
| capacité | résultat |
| ${\begin{aligned}\min &(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=\\&\min(3-0,2-0,1-0)=\\&\min(3,2,1)=1\end{aligned}}$ | $A,D,E,G$ (longueur 4) |
| ${\begin{aligned}\min &(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=\\&\min(3-1,6-0,9-0)=\\&\min(2,6,9)=2\end{aligned}}$ | $A,D,F,G$ (longueur 4) |
| ${\begin{aligned}\min &(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=\\&\min(3-0,4-0,1-0,6-2,9-2)=\\&\min(3,4,1,4,7)=1\end{aligned}}$ | $A,B,C,D,F,G$ (longueur 6) |
| ${\begin{aligned}\min &(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=\\&\min(3-1,4-1,2-0,0-(-1),6-3,9-3)=\\&\min(2,3,2,1,3,6)=1\end{aligned}}$ | $A,B,C,E,D,F,G$ (longueur 6) |

On peut observer que la longueur du chemin augmentant croît, et que les chemins trouvés sont les plus courts possible (en nombre d'arcs). Le théorème flot-max/coupe-min stipule que le flot trouvé, dont la valeur est 5, est égal à la valeur d'une coupe minimum séparant la source du puits. Dans l'exemple une coupe partitionne les sommets en $\{A,B,C,E\}$ et $\{D,F,G\}$, et sa capacité est

    $c(A,D)+c(C,D)+c(E,G)=3+1+1=5$.

## Pseudo-code

Une description de plus haut niveau est donnée dans l'algorithme de Ford-Fulkerson.

