Algoritme de Edmonds-Karp

En ciències de la computació i teoria de grafos, el Algoritme de Edmonds-Karp és una implementació del método de Ford-Fulkerson per a calcular el fluix maximal en una ret de fluix(i.i. computer network) en complexitat O(V I²). És asintóticamente més llent que l'algoritme de Push-relabel, que té complexitat O(V³), pero és habitualment més ràpit en la pràctica per a grafos ralos. L'algoritme va ser publicat per primera volta per un científic soviètic, Yefim (Chaim) Dinic, en 1970, i independentment per Jack Edmonds i Richard Karp en 1972. l'Algoritme de Dinic inclou tècniques adicionals per a reduir la complexitat a O(V²I).

Algoritme

L'algoritme és idèntic al algoritme de Ford-Fulkerson, llevat perque l'orde per a anar buscant els camins aumentantes està definit. El camí trobat deu ser el camí més curt que té capacitat disponible. Açò es pot trobar per mig d'una busca en esgambi, ya que deixem que les vores tinguen unitat de llongitut. La complexitat O(V I²) es fonamenta mostrant que cada camí aumentante pot ser trobat en O(I), cada volta que a lo manco un dels costats I se satura, la distància des del costat saturat fins a l'orige a través del camí aumentante deurà ser més llarc que l'última volta que est va estar saturat, i eixe llarc és com a molt V. Una atra propietat d'este algoritme és que el llarc del camí aumentante més curt s'incrementa monotonamente. Hi ha una prova accessible en:.

Pseudocódigo

Per a una descripció de més alt nivell vore Algoritme de Ford-Fulkerson.

algoritme EdmondsKarp
    entrada:
        C[1..n, 1..n] (matrius de capacitat)
        I[1..n, 1..?] (llista de veïns)
        s             (orige)
        t             (afonament)
    eixida:
        f             (valor del fluix maximal)
        F             (Una matrix que dona un fluix valgut en el màxim valor)
    f := 0 (el fluix inicialment és zero)
    F := array(1..n, 1..n) (Capacitat del residu d'o a v és C[o,v] - F[o,v])
    forever
        m, P := BFS(C, I, s, t, F)
        if m = 0
            break
        f := f + m
        (Busca usant backtracking i estrictura del fluix)
        v := t
        while v ≠ s
            o := P[v]
            F[o,v] := F[o,v] + m
            F[v,o] := F[v,o] - m
            v := o
    return (f, F)

algoritme BFS
    entrada:
        C, I, s, t, F
    eixida:
        M[t]          (Capacitat del camí trobat)
        P             (Taula de pares)
    P := array(1..n)
    for o in 1..n
        P[o] := -1
    P[s] := -2 (assegurar-se de que el 'orige' no siga reemplaçat) 
    M := array(1..n) (Capacitat del camí trobat fins al nodo)
    M[s] := ∞
    Q := queue()
    Q.push(s)
    while Q.size() > 0
        o := Q.pop()
        for v in I[o]
            (Si hi ha capacitat disponible, i v no va ser usat abans en la busca)

if C[o,v] - F[o,v] > 0 and P[v] = -1

                P[v] := o
                M[v] := min(M[o], C[o,v] - F[o,v])
                if v ≠ t
                    Q.push(v)
                else
                    return M[t],
    P return 0,

P == Eixemple == Donat un grafo dirigit (network) de 7 nodos, orige A, afonament G, i les capacitats que es mostren davall:

En els parells $f/c$ escrits en els costats , $f$ és el fluix actual, i $c$ és la capacitat. La capacitat de la resta entre $u$ i $v$ és $c_f(u,v)=c(u,v)-f(u,v)$, la capacitat total, menys el fluix que està en us. Si el fluix des de $u$ a $v$ és negatiu, açò contribuïx a la capacitat del residu.

Capacitat	Camí
	Network resultant
$\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$	$A,D,E,G$
$\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$	$A,D,F,G$
$\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$	$A,B,C,D,F,G$
$\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$	$A,B,C,E,D,F,G$

Notar com la llongitut del Camí Aumentante trobat per l'algoritme mai es decrementa. Els camins trobats són lo més curts possibles. El fluix trobat és igual a la capacitat a travès de tall mínim en el grafo separant l'orige de l'afonament. Hi ha un sol tall minimal en este grafo, particionando els nodos en els conjunts $\{A,B,C,E\}$ i $\{D,F,G\}$, en la capacitat: $c(A,D)+c(C,D)+c(E,G)=3+1+1=5.$