Algoritmus Edmonds – Karp - Edmonds–Karp algorithm

v počítačová věda, Algoritmus Edmonds – Karp je implementace Ford-Fulkersonova metoda pro výpočet maximální průtok v toková síť v ${ displaystyle O}$ ${ displaystyle (| V || E | ^ {2})}$ čas. Algoritmus poprvé publikoval Yefim Dinitz (jehož jméno je také přepsáno „E. A. Dinic“, zejména jako autor jeho raných článků) v roce 1970^[1]^[2] a nezávisle publikoval Jack Edmonds a Richard Karp v roce 1972.^[3] Dinicův algoritmus zahrnuje další techniky, které snižují dobu běhu na ${ displaystyle O (| V | ^ {2} | E |)}$ .^[2]

Algoritmus

Algoritmus je totožný s Algoritmus Ford-Fulkerson, kromě toho, že pořadí hledání při hledání rozšiřující cesta je definováno. Nalezená cesta musí být nejkratší cestou, která má dostupnou kapacitu. To lze najít pomocí a vyhledávání na šířku, kde na každou hranu aplikujeme váhu 1. Provozní doba ${ displaystyle O (| V || E | ^ {2})}$ je nalezen tím, že ukazuje, že každou rozšiřující cestu lze najít v ${ displaystyle O (| E |)}$ čas, že pokaždé, když alespoň jeden z ${ displaystyle E}$ hrany jsou nasycené (hrana, která má maximální možný tok), že vzdálenost mezi nasycenou hranou a zdrojem podél rozšiřující dráhy musí být delší než naposledy, kdy byla nasycena, a že délka je maximálně ${ displaystyle | V |}$ . Další vlastností tohoto algoritmu je to, že délka nejkratší rozšiřující dráhy se monotónně zvyšuje. K dispozici je přístupný důkaz Úvod do algoritmů.^[4]

Pseudo kód

algoritmus EdmondsKarp je    vstup: graf (graf [v] by měl být seznam hran vycházejících z vrcholu v v                 původní graf a jejich odpovídající konstruované zadní hrany                 které se používají pro zpětný tok.                 Každá hrana by měla mít kapacitu, průtok, zdroj a jímku jako parametry,                 a také ukazatel na zadní hranu.)        s (Zdrojový vrchol)        t (Sink vertex)    výstup: tok (Hodnota maximálního průtoku)        průtok: = 0 (Inicializovat tok na nulu)    opakovat        (Spusťte vyhledávání na šířku (bfs) a najděte nejkratší cestu s-t.         Používáme 'pred' k uložení hrany, kterou jsme dostali, abychom se dostali ke každému vrcholu,         abychom mohli cestu později obnovit)        q: = fronta() q.push (s) pred: = pole(délka grafu) zatímco ne empty (q) cur: = q.pull () pro Edge e v graf [aktuální] dělat                -li pred [e.t] = nula a e.t ≠ s a e.cap> e.flow pak                    pred [e.t]: = e q.push (e.t) -li ne (pred [t] = null) pak            (Našli jsme rozšiřující cestu.             Podívejte se, kolik toku můžeme poslat)             df: = ∞            pro (e: = pred [t]; e ≠ null; e: = pred [e.s]) dělat                df: = min(df, e.cap - e.flow) (A aktualizovat hrany o tuto částku)            pro (e: = pred [t]; e ≠ null; e: = pred [e.s]) dělat                e.flow: = e.flow + df e.rev.flow: = e.rev.flow - df flow: = flow + df dokud pred [t] = null (tj. dokud nebyla nalezena žádná rozšiřující cesta)    vrátit se tok

Příklad

Vzhledem k síti sedmi uzlů, zdroj A, jímka G a kapacity, jak je uvedeno níže:

Ve dvojicích ${ displaystyle f / c}$ napsáno na okrajích, ${ displaystyle f}$ je tok proudu a ${ displaystyle c}$ je kapacita. Zbytková kapacita z ${ displaystyle u}$ na ${ displaystyle v}$ je ${ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}$ , celková kapacita, minus již použitý průtok. Pokud síť teče z ${ displaystyle u}$ na ${ displaystyle v}$ je negativní, to přispívá na zbytkovou kapacitu.

Kapacita	Cesta	Výsledná síť
${ displaystyle { begin {zarovnáno} & 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 konec {zarovnáno}}}$	${ displaystyle A, D, E, G}$
${ displaystyle { begin {zarovnáno} & 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 end {zarovnáno}}}$	${ displaystyle A, D, F, G}$
${ displaystyle { begin {aligned} & 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 end {zarovnáno}}}$	${ displaystyle A, B, C, D, F, G}$
${ displaystyle { begin {aligned} & 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 konec {zarovnáno}}}$	${ displaystyle A, B, C, E, D, F, G}$

Všimněte si, jak je délka rozšiřující cesta nalezený algoritmem (červeně) se nikdy nesnižuje. Nalezené cesty jsou nejkratší možné. Nalezený tok se rovná kapacitě napříč minimální řez v grafu oddělujícím zdroj a jímku. V tomto grafu je pouze jeden minimální řez, který rozděluje uzly do sad ${ displaystyle {A, B, C, E }}$ a ${ displaystyle {D, F, G }}$ , s kapacitou