Algoritmul Edmonds-Karp

Algoritmul Edmonds-Karp, publicat de Jack Edmonds și Richard Karp reprezintă o implementare eficientă a algoritmului Ford Fulkerson.

Ideea care stă la baza algoritmului este de a identifica la fiecare pas un drum de creștere care conține un număr minim de arce. După cum vom arăta în continuare, o astfel de alegere ne asigură că se vor efectua cel mult Θ(M • N) iterații.

Fiecare drum de creștere conține, așa cum rezultă din definiție, cel puțin un arc critic (arcul care dă valoarea diurnului). Să presupunem că arcul (i, j) apare pentru prima dată ca arc critic într-un drum de creștere în momentul în care acesta se află la distanta d de sursă (este al d-lea arc de pe drumul de creștere). Se poate arăta faptul că, alegând de fiecare dată un drum de creștere cu număr minim de muchii, în momentul în care arcul (i, j) va apărea pentru a doua oară ca arc critic, el se va afla la o distantă de cel puțin d + 2 de sursă. Ca urmare, fiecare arc (i, j) va putea fi arc critic de cel mult [N / 2] ori pe parcursul executării algoritmului, așadar vom avea cel mult Θ(N) drumuri de creștere caracterizate prin arcul critic (i,j). Deoarece avem 2 • M arce (incluzându-le pe cele speciale), în total vor exista cel mult Θ(M • N) drumuri de creștere, deci ordinul de complexitate al algoritmului Edmonds-Karp va fi Θ((M + N) • M • N), deoarece parcurgerea în lățime necesară identificării unui drum de creștere are ordinul de complexitate Θ(M + N).

Implementare

Implementare în pseudocod

algoritmul EdmondsKarp
    input:
        C[1..n, 1..n] (Capacity matrix)
        E[1..n, 1..?] (Neighbour lists)
        s             (Source)
        t             (Sink)
    output:
        f             (Value of maximum flow)
        F             (A matrix giving a legal flow with the maximum value)
    f := 0 (Initial flow is zero)
    F := array(1..n, 1..n) (Residual capacity from u to v is C[u,v] - F[u,v])
    forever
        m, P := BreadthFirstSearch(C, E, s, t)
        if m = 0
            break
        f := f + m
        (Backtrack search, and write flow)
        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
    output:
        M[t]          (Capacity of path found)
        P             (Parent table)
    P := array(1..n)
    for u in 1..n
        P[u] := -1
    P[s] := -2 (make sure source is not rediscovered) 
    M := array(1..n) (Capacity of found path to node)
    M[s] := ∞
    Q := queue()
    Q.push(s)
    while Q.size() > 0
        u := Q.pop()
        for v in E[u]
            (If there is available capacity, and v is not seen before in search)
            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

Implementare Python

def edmonds_karp(C, source, sink):
    n = len(C) # C is the capacity matrix
    F = 0 * n for i in xrange(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]

    while True:
        path = bfs(C, F, source, sink)
        if not path:
            break
        flow = float(1e309) # Infinity
        # traverse path to find smallest capacity
        for (u,v) in path:
            flow = min(flow, C[u][v] - F[u][v])
        # traverse path to update flow
        for u,v in path:
            F[u][v] += flow
            F[v][u] -= flow
    return sum([F[source][i] for i in xrange(n)])

def bfs(C, F, source, sink):
    queue = [source]                 
    paths = {source: []}
    while queue:
        u = queue.pop(0)
        for v in xrange(len(C)):
            if C[u][v] - F[u][v] > 0 and v not in paths:
                paths[v] = paths[u] + [(u,v)]
                if v == sink:
                    return paths[v]
                queue.append(v)
    return None