Edmonds-Karpův algoritmus

Algoritmus Edmonds-Karp řeší problém nalezení maximálního toku v transportní síti . Algoritmus je speciálním případem Ford-Fulkersonovy metody a běží v čase v grafu . Poprvé ji publikoval v roce 1970 sovětský vědec E. A. Dinitz . Později, v roce 1972, byl nezávisle objeven Edmondsem a Karpem . $O(|V|\cdot |E|^{2})$ $G=(V,E)$

Algoritmus

Algoritmus Edmonds-Karp je variantou algoritmu Ford-Fulkerson, ve kterém se v každém kroku volí nejkratší komplementární cesta z do ve zbytkové síti (za předpokladu, že každá hrana má jednotkovou délku). Nejkratší cesta se najde hledáním do šířky . $s$ $t$

Popis

Obnovili jsme všechny streamy. Zbytková síť se zpočátku shoduje s původní sítí.
Ve zbytkové síti najdeme nejkratší cestu od zdroje k jímce. Pokud taková cesta není, zastavíme se.
Necháme přes nalezenou cestu (říká se tomu rostoucí cesta nebo rostoucí řetězec ) maximální možný tok:
1. Na nalezené cestě ve zbytkové síti hledáme hranu s minimální kapacitou . $c_{\min }$
2. Pro každou hranu na nalezené cestě průtok zvýšíme o , v opačném směru snížíme o . $c_{\min }$ $c_{\min }$
3. Upravujeme zbytkovou síť. Pro všechny hrany na nalezené cestě i pro hrany k nim protilehlé vypočítáme novou kapacitu. Pokud bude nenulová, přidáme do zbytkové sítě hranu, a pokud bude nulová, vymažeme ji.
Vrátíme se ke kroku 2.

K nalezení nejkratší cesty v grafu používáme vyhledávání na šířku :

Vytvoříme frontu vrcholů O. Zpočátku , O sestává z jediného vrcholu s .
Vrchol s označíme jako navštívený, bez rodiče a všechny ostatní jako nenavštívené.
Dokud fronta není prázdná, proveďte následující kroky:
1. Smažte první vrchol ve frontě u .
2. Pro všechny oblouky ( u , v ) vycházející z vrcholu u , pro které vrchol v ještě nebyl navštíven, proveďte následující kroky:
  1. Vrchol v označíme jako navštívený s nadřazeným u .
  2. Přidejte vrchol v na konec fronty.
  3. Pokud v = t , opusťte obě smyčky: našli jsme nejkratší cestu.
Pokud je fronta prázdná, vrátíme odpověď, že cesta vůbec nevede a zastavíme.
Pokud ne, přejdeme z t do s , pokaždé přejdeme k rodiči. Cestu vracíme v obráceném pořadí.

Obtížnost

V průběhu práce Edmonds-Karpův algoritmus najde každou komplementární cestu v čase . Níže ukážeme, že celkový počet zvýšení průtoku provedených tímto algoritmem je . Složitost Edmonds-Karpova algoritmu je tedy . $O(|E|)$ $O(|V|\cdot |E|)$ $O(|V|\cdot |E|^{2})$

Důkaz

Nazvěme vzdálenost od vrcholu x k vrcholu y délkou nejkratší cesty z x do y ve zbytkové síti, měřenou počtem hran. Pokud taková cesta neexistuje, budeme vzdálenost považovat za nekonečnou. Řekneme, že y se přiblížilo x (odchýlilo se od x ), pokud se vzdálenost od x k y zmenšila (zvětšila). Řekneme, že y je blíže k x (dále od x ) než z , pokud je vzdálenost x k y menší (větší) než vzdálenost x k z .

Lemma . V průběhu algoritmu se žádný vrchol nikdy nepřiblíží ke zdroji. Důkaz . Ať tomu tak není, pak se s určitým zvýšením průtoku některé vrcholy přiblížily ke zdroji. Nazvěme je špatně. Vybereme jeden ze špatných vrcholů, který se po zvýšení průtoku ukázal být nejblíže zdroji (pokud jich je více, tak kterýkoli). Označte vybraný vrchol v . Uvažujme nejkratší cestu z s do v . Předposlední vrchol na této cestě označte u , takže cesta vypadá jako . Protože u je blíže k s než v a v je nejbližší nelegální vrchol k s , pak u je pravidelný vrchol. Značíme-li vzdálenosti od s do u a v před a po nárůstu toku, respektive jako , , , , máme: $s-\ldots-uv$ $d_{u}\$ ${\displaystyle d_{u}^{'))$ $d_{v}\$ ${\displaystyle d_{v}^{'))$

d_{v}^{'}<d_{v}

{\displaystyle d_{u}^{'}\geq d_{u))

d_{v}^{'}=d_{u}^{'}+1

kde

d_{v}\geq d_{u}+2

Proto před zvýšením průtoku ve zbytkové síti chyběl oblouk ( u , v ). Aby se objevila, musela rozšiřující cesta obsahovat oblouk ( v , u ). Ale v Edmonds-Karpově algoritmu je rozšiřující cesta vždy nejkratší, takže

d_{v}=d_{u}-1

což odporuje předchozí nerovnosti. Náš předpoklad byl tedy mylný. Lema je dokázáno.

Nazvěme kritické , že okraje augmentační cesty, jejichž zbytková kapacita je minimální. Odhadněme, kolikrát může být některá hrana (u, v) kritická. Ať se to stane při iteraci a příště při iteraci . Označením vzdálenosti od s do y v iteraci t máme: $t_{1}$ $t_{2}$ $D_{y}(t)$

D_{v}(t_{1})=D_{u}(t_{1})+1

D_{v}(t_{2})=D_{u}(t_{2})+1

Všimněte si, že při iteraci kritická hrana zmizí ze zbytkové sítě. Aby se v něm hrana (u, v) do doby iterace znovu objevila, je nutné, aby při nějaké mezi iteraci byla zvolena rozšiřující cesta obsahující hranu (v, u). Tudíž, $t_{1}$ $t_{2}$ ${\displaystyle t_{3))$

D_{u}(t_{3})=D_{v}(t_{3})+1

Pomocí dříve osvědčeného lemmatu dostaneme:

D_{v}(t_{2})=D_{u}(t_{2})+1\geq D_{u}(t_{3})+1=D_{v}(t_{3} )+2\geq D_{v}(t_{1})+2

Protože zpočátku (jinak v = s, ale hrana vedoucí k s se nemůže objevit na nejkratší cestě od s do t) a vždy, když je samozřejmě menší než |V| (nejkratší cesta neobsahuje cykly, a proto obsahuje méně |V| hran), hrana může být ve většině případů kritická. Protože každá rozšiřující cesta obsahuje alespoň jednu kritickou hranu a celkový počet hran, které se jednoho dne mohou stát kritickými (všechny hrany původní sítě a jejich protilehlé), pak můžeme cestu zvětšit maximálně |E|·|V | jednou. Počet iterací tedy nepřesahuje O(|E|·|V|), což bylo třeba dokázat. $D_{v}>0$ ${\displaystyle D_{v))$ ${\frac {(|V|-1)-1}{2}}+1=|V|/2$ $2|E|$

Příklad

Nechť je dána síť se zdrojem ve vrcholu a mozkem ve vrcholu . Na obrázku dvojice označuje tok podél této hrany a její průchodnost. $A$ $G$ $f/c$

Šířka první hledání

Popišme v prvním kroku prohledávání do šířky.

Fronta se skládá z jednoho vrcholu A. Byl navštíven vrchol A. Neexistuje žádný rodič.
Fronta se skládá (od začátku do konce) z vrcholů B a D. Navštíví se vrcholy A, B, D. Vrcholy B, D mají rodiče A.
Fronta se skládá z vrcholů D a C. Navštíveno A, B, C, D. Vrcholy B, D mají nadřazený A, vrchol C má nadřazený B.
Fronta se skládá z vrcholů C, E, F. Navštívené A, B, C, D, E, F. Vrcholy B, D mají rodiče A, vrchol C má rodič B, vrcholy E, F mají rodiče D.
Vertex C je odstraněn z fronty: jeho okraje vedou pouze k již navštíveným vrcholům.
Je nalezena hrana (E,G) a smyčka se zastaví. Vrcholy (F,G) jsou ve frontě. Všechny navštívené vrcholy. Vrcholy B, D mají rodiče A, vrchol C má rodič B, vrcholy E, F mají rodiče D a vrchol G má rodič E.
Jdeme podle rodičů: . Prošlou cestu vracíme v obráceném pořadí: . $G\to E\to D\to A$ $A\to D\to E\to G$

Všimněte si, že vrcholy dosažitelné z A přesně v 1 kroku, přesně ve 2 krocích a přesně ve 3 krocích byly postupně přidány do fronty. Kromě toho je rodičem každého vrcholu vrchol dosažitelný z A přesně o 1 krok rychleji.

Základní algoritmus

Kapacita cesty	Cesta
Kapacita cesty
$\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$	$A,D,E,G$

$\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$	$A,D,F,G$

$\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$	$A,B,C,D,F,G$

$\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$	$A,B,C,E,D,F,G$

Všimněte si, že během provádění algoritmu se délky komplementárních cest (na obrázcích označeny červeně) nezmenšují. Tato vlastnost je splněna díky tomu, že hledáme nejkratší doplňkovou cestu .

Dinitzův algoritmus

Vylepšená verze Edmonds-Karpova algoritmu je Dinitzův algoritmus, který vyžaduje operace. $O(|V|^{2}|E|)$

Pomocnou bezobrysovou síť grafu G se zdrojem s nazveme jejím podgrafem obsahujícím pouze ty hrany (u, v), pro které je minimální vzdálenost od s k v o jednu větší než minimální vzdálenost od s k u.

Dinitův algoritmus:

Sestrojíme minimální bezkonturovou síť zbytkového grafu.
Pokud je v síti cesta od s do t, proveďte následující kroky:
1. Najděte nejkratší cestu z s do t. Pokud neexistuje, opusťte smyčku.
2. Na nalezené cestě ve zbytkové síti hledáme hranu s minimální kapacitou . $c_{\min }$
3. Pro každou hranu na nalezené cestě průtok zvýšíme o , v opačném směru snížíme o . $c_{\min }$ $c_{\min }$
4. Vymažeme všechny hrany, které dosáhly saturace.
5. Vymažeme všechny slepé uličky (tedy vrcholy, kromě propadu, ze kterého nejdou žádné hrany, a vrcholy kromě zdroje, kam žádné hrany nevstupují), spolu se všemi hranami, které k nim patří.
6. Opakujte předchozí krok, dokud je co odstranit.
Pokud je nalezený proud nenulový, přidejte jej k celkovému proudu a vraťte se ke kroku 1.

Odkazy

Literatura

Thomas Kormen aj. Algoritmy: konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Algoritmy pro vyhledávání grafů
Neinformované metody	Obousměrné vyhledávání Hledání paprskem Lexikografická šířka první hledání Šířka první hledání Vyhledávání podle nákladového kritéria Hloubka první hledání Zpětné vyhledávání Hledejte podle výstupu na vrchol Hloubkově omezené hledání Hloubkové vyhledávání s iterativním prohlubováním
Informované metody	Výstřižek alfa beta Metoda větvení a vazby Hledejte podle první nejlepší shody A* B* D* Hledání přechodového bodu IDA* Rekurzivní vyhledávání první nejlepší shody SMA*
Zkratky	Vlnový algoritmus Bellman-Fordův algoritmus Dijkstrův algoritmus Johnsonův algoritmus Levitův algoritmus Floyd-Warshall algoritmus Hledání okrajů
Minimální kostra	Borůvkův algoritmus Primův algoritmus Kruskalův algoritmus
jiný	Algoritmus Britského muzea Edmondsův algoritmus Přechod stromu Algoritmus nejbližšího souseda v problému obchodního cestujícího