Algorithme d'Edmonds-Karp

Pour les articles homonymes, voir Algorithme d'Edmonds.

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²). 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³), 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² 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²) 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].

Exemple

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

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

${\displaystyle 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 ${\displaystyle u}$ vers ${\displaystyle v}$ est supérieur à la capacité, la capacité résiduelle est négative, et sa contribution est négative.

capacité	chemin
	résultat
${\displaystyle {\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}}}$	${\displaystyle A,D,E,G}$ (longueur 4)
${\displaystyle {\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}}}$	${\displaystyle A,D,F,G}$ (longueur 4)
${\displaystyle {\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}}}$	${\displaystyle A,B,C,D,F,G}$ (longueur 6)
${\displaystyle {\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}}}$	${\displaystyle 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 ${\displaystyle \{A,B,C,E\}}$ et ${\displaystyle \{D,F,G\}}$, et sa capacité est

${\displaystyle 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.

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 capacité 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

Notes et références

Bibliographie

• 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, n^o 2,‎ 1972, 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, 2001, 2^e é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, 2^e édition, Dunod 2002, « chapitre 26. Flot Maximum ».

Lien externe

Il existe de nombreux textes accessibles en ligne, dont :

• Algorithms and Complexity (pages 63–69) du cours de Herbert Wilf
• Bobby Kleinberg, « Edmonds-Karp Max-Flow Algorithm », sur université Cornell.

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