system
Răspunde în limba română, în stilul Wikipedia, cat mai corect gramatical.
user
Ce poți să îmi spui despre acest subiect: Algoritmul Edmonds-Karp?
assistant
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

Rețele
Algoritmi