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 E2). Il est asymptotiquement plus lent que l'algorithme de poussage/reétiquetage[1] qui utilise une heuristique basée sur une pile et qui est en temps O(V3), 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[2] puis et indépendamment par Jack Edmonds et Richard Karp en 1972[3]. L'algorithme de Dinic contient un critère de sélection supplémentaire qui réduit le temps de calcul à O(V2 E).

Algorithme

modifier

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 E2) 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[4].

Sur les autres projets Wikimedia :

Exemple

modifier

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

 

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

 ,

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


capacité chemin
résultat

 

  (longueur 4)
 

 

  (longueur 4)
 

 

  (longueur 6)
 

 

  (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   et  , et sa capacité est

 .

Pseudo-code

modifier

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

Notes et références

modifier
  1. La traduction proposée dans la version française du livre de Cormen et al. chapitre 26.5. est réétiqueter-vers-l'avant.
  2. Dinic 1970
  3. Edmonds et Karp 1972
  4. Cormen et al. 2001, chap. 26.2.
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Edmonds–Karp algorithm » (voir la liste des auteurs).

Bibliographie

modifier
  • E. A. Dinic, « Algorithm for solution of a problem of maximum flow in a network with power estimation », Soviet Math. Doklady, Doklady Nauk SSSR, vol. 11,‎ , p. 1277–1280 (lire en ligne). Traduction anglaise de l’article russe paru la même année.
  • Jack Edmonds et Richard M. Karp, « Theoretical improvements in algorithmic efficiency for network flow problems », Journal of the ACM, Association for Computing Machinery (ACM), vol. 19, no 2,‎ , p. 248–264 (DOI 10.1145/321694.321699).
  • (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge, MIT Press and McGraw-Hill, , 2e éd., 1180 p. (ISBN 978-0-262-53196-2, LCCN 2001031277), chap. 26 (« Chap. 26 Flows »), p. 643–700. Traduction française : Introduction à l'algorithmique, 2e édition, Dunod 2002, « chapitre 26. Flot Maximum ».

Lien externe

modifier

Il existe de nombreux textes accessibles en ligne, dont :