Dinitův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. května 2021; kontroly vyžadují 3 úpravy .

Dinitzův algoritmus je polynomiální algoritmus pro nalezení maximálního toku v dopravní síti , navržený v roce 1970 sovětským (později izraelským) matematikem Efimem Dinitzem . Časová složitost algoritmu je . Takový odhad lze získat zavedením pojmů pomocná síť a blokující (pseudomaximální) tok . V sítích s jednotkovou šířkou pásma existuje silnější odhad časové složitosti: . $O(|V|^{2}|E|)$ $O(|E||V|)$

Popis

Dovolit být dopravní síť , ve které a jsou, v tomto pořadí, propustnost a tok přes okraj . $G=(V,E,c,s,t)$ $c(u,v)$ $f(u,v)$ $(u,v)$

Zbytková šířka pásma je mapování definované jako:

{\displaystyle c_{f}\colon V\times V\to \mathbb {R} ^{+))

pokud , $(u,v)\in E$ $c_{f}(u,v)=c(u,v)-f(u,v)$ $c_{f}(v,u)=f(u,v)$ V jiných zdrojích $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$
$c_{f}(u,v)=0$ v opačném případě.

Zbytková síť - graf , kde

G_{f}=(V,E_{f},c_{f}|_{E_{f)),s,t)

{\displaystyle E_{f}=\{(u,v)\in V\times V\mid c_{f}(u,v)>0\))

. Doplňková cesta je cesta v grafu reziduí .

st

G_f

Nechť je délka nejkratší cesty z do v grafu . Pak pomocnou sítí grafu je graf , kde

\operatorname {dist} (v)

s

proti

G_f

G_f

G_{L}=(V,E_{L},c_{f}|_{E_{L)),s,t)

{\displaystyle E_{L}=\{(u,v)\in E_{f}\mid \operatorname {dist} (v)=\operatorname {dist} (u)+1\))

. Blokující tok je takový tok , že graf c neobsahuje cestu.

st

F

G'=(V,E_{L}',c_{f}|_{E_{L)),s,t)

E_{L}'=\{(u,v)\mid f(u,v)<c_{f}|_{E_{L}}(u,v)\}

st

Algoritmus

Dinitův algoritmus

Vstup : Síť .

G=(V,E,c,s,t)

Výstup : maximální průtok .

st

F

Nainstalujte pro každý . $f(e)=0$ $e\in E$
Vytvořit z grafu . Pokud , zastavte a vystupte . $G_L$ $G_f$ $G$ $\operatorname {dist} (t)=\infty$ $F$
Najděte blokující vlákno v . $F'$ $G_L$
Rozšiřte tok o tok a přejděte ke kroku 2. $F$ $F'$

Analýza

Je možné ukázat, že pokaždé, když se počet hran na nejkratší cestě od zdroje k jímce zvýší alespoň o jednu, takže v algoritmu již nejsou žádné blokující toky, kde je počet vrcholů v síti. Pomocná síť může být vybudována procházením v čase do šířky a blokovací tok na každé úrovni grafu lze nalézt v čase . Proto je doba běhu algoritmu Dinits . $n-1$ $n$ $G_L$ $O(|V|+|E|)$ $O(|V||E|)$ $O(|V|)\cdot (O(|V|+|E|)+O(|V||E|))=O(|V|^{2}|E|)$

Pomocí datových struktur nazývaných dynamické stromy je možné najít blokující tok v každé fázi v čase , poté lze dobu běhu Dinitzova algoritmu zlepšit na . $O(|E|\log |V|)$ $O(|V||E|\log |V|)$

Příklad

Níže je simulace Dinitzova algoritmu. V pomocné síti jsou vrcholy s červenými štítky hodnotami . Blokovací závit je označen modře. $G_L$ $\operatorname {dist} (v)$

	$G$	$G_f$	$G_L$
jeden.
	Blokující vlákno se skládá z cest: $\{s,1,3,t\}$ se 4 průtokovými jednotkami, $\{s,1,4,t\}$ se 6 průtokovými jednotkami a $\{s,2,4,t\}$ se 4 průtokovými jednotkami. Blokující tok tedy obsahuje 14 jednotek a hodnota toku je 14. Všimněte si, že doplňková cesta má 3 hrany. $\|f\|$
2.
	Blokující vlákno se skládá z cest: $\{s,2,4,3,t\}$ s 5 průtokovými jednotkami. Blokující tok tedy obsahuje 5 jednotek a hodnota toku je 14 + 5 = 19. Všimněte si, že komplementární cesta má 4 hrany. $\|f\|$
3.
	Akcie nejsou dostupné v síti . Proto se algoritmus zastaví a vrátí maximální tok o velikosti 19. Všimněte si, že v každém blokovacím toku se počet hran v komplementární cestě zvýší alespoň o jednu. $t$ $G_f$

Historie

Dinitzův algoritmus byl publikován v roce 1970 bývalým sovětským vědcem Efimem Dinitzem, který je nyní členem Fakulty počítačového inženýrství na Ben-Gurionově univerzitě (Izrael), dříve než algoritmus Edmonds-Karp , který byl publikován v roce 1972, ale vytvořené dříve. Nezávisle na sobě ukázali, že v případě Ford-Fulkersonova algoritmu , pokud je komplementární cesta nejkratší, délka komplementární cesty se nezmenšuje.

Dinitzův algoritmus s propagací

Časovou složitost algoritmu lze snížit optimalizací procesu hledání blokujícího vlákna. K tomu je nutné zavést pojem potenciál . Okrajový potenciál je a vrcholový potenciál je . Podle stejné logiky a . Myšlenkou vylepšení je hledat v pomocné síti vrchol s minimálním kladným potenciálem a pomocí front vybudovat blokovací tok přes něj . $e\in E$ $\operatorname {pot} (e)=c_{f}(e)$ ${\displaystyle v\in V\setminus \{s,t\))$ $\operatorname {pot} (v)=\min\{\součet _{e\in \delta ^{+}(v)}\operatorname {pot} (e),\součet _{e\in \ delta ^{-}(v)}\operatorname {pot} (e)\}$ $\operatorname {pot} (s)=\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e)$ $\operatorname {pot} (t)=\sum _{e\in \delta ^{-}(v)}\operatorname {pot} (e)$

Vstup : Síť .

G=(V,E,c,s,t)

Výstup : maximální průtok .

st

F

Nainstalujte pro každý . $f(e)=0$ $e\in E$
Vytvořit z grafu . Pokud , zastavte a vystupte . $G_L$ $G_f$ $G$ $\operatorname {dist} (s,t)=\infty$ $F$
Nainstalujte pro každý . $f'(e)=0$ $e\in E$
Určete potenciál každého vrcholu.
Dokud existuje vrchol takový, že : $v\in V$ $\operatorname {pot} (v)>0$
1. Definujte tok pomocí dopředného šíření z . $F''$ $proti$
2. Určete tok pomocí zpětného šíření z . $f'''$ $proti$
3. Doplňte stream o proudy a . $F'$ $F''$ $f'''$
Rozšiřte tok o tok a přejděte ke kroku 2. $F$ $F'$

Algoritmy dopředného a zpětného šíření slouží k nalezení cest z do az do . Příklad algoritmu přímého šíření pomocí front: $proti$ $t$ $s$ $proti$

Vstup : Pomocná síť , vrchol takový, že .

G_{L}=(V,E_{L},c_{f}|_{E_{L)),s,t)

v\in V

\operatorname {pot} (v)>0

Výstup : Tok od zdroje k vrcholu , který je součástí blokujícího toku.

F''

s

proti

Instalovat pro všechny : . ${\displaystyle w\in V\setminus \{v\))$ $U(w)=0$
Nainstalujte a . $U(v)=\operatorname {pot} (v)$ $\operatorname {pot} (v)=0$
Přidat do fronty . $proti$ $Q$
Dokud fronta není prázdná: $Q$
1. Nastavte hodnotu na poslední prvek fronty. $proti$
2. ahoj : $U(v)>0$
  1. Pro každou hranu : $e=(v,w)\in \delta ^{+}(v)$
  2. ${\displaystyle f''(e)=\min\{\jméno operátora {pot} (e),U(v)\))$ .
  3. Aktualizovat . $U(v)=U(v)-f''(e)$
  4. Aktualizovat . $U(w)=U(w)+f''(e)$
  5. Nainstalujte . $\operatorname {pot} (w)=\operatorname {pot} (w)-\operatorname {pot} (e)$
  6. Pokud a vyřadit z fronty _ $w\neq t$ $U(w)=f''(e)$ $w$ $Q$

Vzhledem k tomu, že v každé iteraci hledání blokujícího toku je "nasycen" alespoň jeden vrchol, je dokončován v nejhorších iteracích, z nichž každý bere v úvahu maximum vrcholů. Nechť je počet "nasycených" hran v každé -té iteraci hledání blokujícího vlákna. Pak je jeho asymptotická složitost , kde je počet vrcholů a počet hran v grafu. Asymptotická složitost Dinitzova algoritmu šíření je tedy rovna , protože blokovací tok může procházet nanejvýš vrcholy. $|V|-1$ $|V|$ $l_{i}$ $i$ $\sum _{i=1}^{n-1}O(n+l_{i})=O(n^{2}+\sum _{i=1}^{n-1}l_ {i})=O(n^{2}+m)$ $n$ $m$ $O(|V|^{3})$ $|V|$

Literatura

Jefim Dinitz. Dinitzův algoritmus: Původní verze a Evenova verze // Teoretická informatika: Essays in Memory of Shimon Even (anglicky) / Oded Goldreich, Arnold L. Rosenberg a Alan L. Selman. - Springer, 2006. - S. 218-240. — ISBN 978-3540328803 .
BH Korte, Jens Vygen. 8.4 Blokování toků a Fujishigeho algoritmus // Kombinatorická optimalizace: Teorie a algoritmy (Algorithms and Combinatorics, 21 ) . - Springer Berlin Heidelberg , 2008. - S. 174-176 . — ISBN 978-3-540-71844-4 .

Odkazy

Dinitův algoritmus na e-maxx.ru: Popis, důkazy, implementace v C++