# Algoritmul Edmonds Karp

### De la Wikipedia, enciclopedia liberă

Acest articol trebuie pus în formatul standard.
Puteţi contribui la îmbunătăţirea conţinutului şi a formei sale.

Algoritmul Edmonds-Karp reprezintă doar 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

Adus de la "http://ro.wikipedia.org../../../a/l/g/Algoritmul_Edmonds_Karp_0369.html"

Categorii: Articole de curăţat | Reţele | Matematică | Informatică

##### Views

- Articol
- Discuţie
- Versiunea curentă

##### Caută

##### În alte limbi

- English
- Português