Algoritmul Edmonds Karp
De la Wikipedia, enciclopedia liberă
Acest articol trebuie pus în formatul standard conform manualului de stil.Eticheta aceasta trebuie ştearsă la încheierea standardizării. Articolul a fost etichetat în luna martie 2007.
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).
[modifică] Implementare
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
