Algorithme d'Edmonds-Karp

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[1] 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[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(V 2 E).

Algorithme[modifier | modifier le code]

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 le chemin le plus court qui possède une capacité positive. Un tel chemin peut être trouvé par un parcours en largeur, 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[4].

Pseudocode[modifier | modifier le code]

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

algorithm EdmondsKarp
    input:
        C[1..n, 1..n] (matrice des capacités)
        E[1..n, 1..?] (listes des voisins)
        s             (source)
        t             (puits)
    output:
        f             (valeur du flot maximum)
        F             (matrice donnant un flot valide de valeur maximum)
    f := 0 (le flot initial est nul)
    F := array(1..n, 1..n) (la capacité résiduelle de u à v est C[u,v] - F[u,v])
    forever
        m, P := BreadthFirstSearch(C, E, s, t, F)
        if m = 0
            break
        f := f + m
        (Backtrack et noter le flot)
        v := t
        while v ≠ s
            u := P[v]
            F[u,v] := F[u,v] + m
            F[v,u] := F[v,u] - m
            v := u
    return (f, F)

algorithm BreadthFirstSearch
    input:
        C, E, s, t, F
    output:
        M[t]          (capacité du chemin trouvé)
        P             (table des parents)
    P := array(1..n)
    for u in 1..n
        P[u] := -1
    P[s] := -2 (pour assurer que la source n'est pas redécouverte) 
    M := array(1..n) (capacité du chemin trouvé jusqu'au nœud)
    M[s] := ∞
    Q := queue()
    Q.push(s)
    while Q.size() > 0
        u := Q.pop()
        for v in E[u]
            (s'il y a une capaité disponible, et si v n'a pas été vu durant la recherche)
            if C[u,v] - F[u,v] > 0 and P[v] = -1
                P[v] := u
                M[v] := min(M[u], C[u,v] - F[u,v])
                if v ≠ t
                    Q.push(v)
                else
                    return M[t], P
    return 0, P

Sur les autres projets Wikimedia :

Exemple[modifier | modifier le code]

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 le arcs.

Réseau de départ. Flot nul.

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
résultat

\begin{align}\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{align}

A,D,E,G (longueur 4)
Valeur du flot=1

\begin{align}\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{align}

A,D,F,G (longueur 4)
Valeur du flot=3

\begin{align}\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{align}

A,B,C,D,F,G (longueur 6)
Valeur du flot=4

\begin{align}\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{align}

A,B,C,E,D,F,G (longueur 6)
Valeur du flot=5

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, il n'y a qu'une seule telle coupe; elle 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.

Notes et références[modifier | modifier le code]

  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.

(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 | modifier le code]

  • 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,‎ 1970, 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,‎ 1972, p. 248–264 (lien DOI?).
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge, MIT Press and McGraw-Hill,‎ 2001, 2e éd. (ISBN 978-0-262-53196-2, lien LCCN?), chap. 26 (« chap. 26 Flows »), p. 643–700. Traduction francaise : Introduction à l'algorithmique, 2e édition, Dunod 2002, « chapitre 26. Flot Maximum ».

Lien externe[modifier | modifier le code]

Il existe de nombreux textes accessibles en ligne. En voici un :