Dijkstra: Oprava preklepu

[ga.git] / 2-dinic / 2-dinic.tex

\input ../sgr.tex

\prednaska{2}{Dinicùv algoritmus a jeho varianty}{}

Maximální tok v~síti u¾ umíme najít pomocí Fordova-Fulkersonova algoritmu
z~minulé kapitoly. Nyní pojednáme o~efektivnìj¹ím Dinicovì algoritmu
a o~rùzných jeho variantách pro sítì ve~speciálním tvaru.

\h{Dinicùv algoritmus}

Dinicùv algoritmus je zalo¾en na~následující my¹lence: Ve~Fordovì-Fulkersonovì algoritmu
nemusíme pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující
toky. Nejlépe toky takové, aby je nebylo obtí¾né najít, a~pøitom aby pùvodní tok
dostateènì obohatily. Vhodnými objekty k~tomuto úèelu jsou blokující toky:

\s{Definice:} {\I Blokující tok} je tok takový, ¾e ka¾dá orientovaná $st$-cesta
obsahuje alespoò jednu nasycenou hranu. [Tj. takový tok, který by na¹el F-F algoritmus,
kdyby neuva¾oval rezervy v~protismìru.]

\s{Algoritmus (Dinic):}

\algo
\:Zaèneme s~libovolným tokem~$f$, napøíklad prázdným (v¹ude nulovým).
\:Iterativnì vylep¹ujeme tok pomocí zlep¹ujících tokù: {\I (vnìj¹í cyklus)}
\::Sestrojíme sí» rezerv: vrcholy a hrany jsou tyté¾, kapacity jsou urèeny rezervami v~pùvodní síti.
Dále budeme pracovat s~ní.
\::Najdeme nejkrat¹í $st$-cestu. Kdy¾ ¾ádná neexistuje, skonèíme.
\::Proèistíme sí», tj. ponecháme v ní pouze vrcholy a hrany na nejkrat¹ích $st$-cestách.
\::Najdeme v~proèi¹tìné síti blokující tok $f_B$:
\:::$f_B \leftarrow \<prázdný tok>$
\:::Postupnì pøidáváme $st$-cesty: {\I (vnitøní cyklus)}
\::::Najdeme $st$-cestu. Napø. hladovì -- \uv{rovnou za nosem}.
\::::Po¹leme co nejvíce po~nalezené cestì.
\::::Sma¾eme nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé ulièky,
èím¾ se zneèistí sí» a nebude fungovat hladové hledání cest.)
\::::Doèistíme sí».
\::Zlep¹íme $f$ podle $f_B$
\endalgo

\finalfix{\vskip-3pt}
\figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.4\hsize}
\finalfix{\vskip-6pt}

\s{Slo¾itost algoritmu:}
Oznaème $l$ délku nejkrat¹í $st$-cesty, $n$ poèet vrcholù sítì a $m$ poèet hran sítì.

\itemize\ibull
\:Jeden prùchod vnitøním cyklem trvá $\O(l)$, co¾ mù¾eme odhadnout jako $\O(n)$, proto¾e v¾dy platí $l \leq n$.
\:Vnitøní cyklus se provede maximálnì $m$-krát, proto¾e se v¾dy alespoò jedna hrana nasytí
  a ze sítì vypadne, tak¾e krok~6 mimo podkroku~12 bude trvat $\O(mn)$.
\:Èi¹tìní a doèi¹»ování sítì dohromady provedeme takto:
  \itemize\ibull
  \:Rozvrstvíme vrcholy podle vzdálenosti od $s$.
  \:Zaøízneme dlouhé cesty (del¹í, ne¾ do vrstvy obsahující $t$).
  \:Dr¾íme si frontu vrcholù, které mají $\deg^+ = 0$ èi $\deg^- = 0$.
  \:Vrcholy z~fronty vybíráme a zahazujeme vèetnì hran, které vedou do/z nich.
    A pøípadnì pøidáváme do~fronty vrcholy, kterým pøi tom klesl jeden ze stupòù na 0.
    Vyma¾ou se tím slepé ulièky, které by vadily v podkroku~9.
  \endlist
  Takto kroky 5 a 12 dohromady spotøebují èas $\O(m)$.
  \:Jeden prùchod vnìj¹ím cyklem tedy trvá $\O(mn)$.
  \:Jak za chvíli doká¾eme, ka¾dým prùchodem vnìj¹ím cyklem $l$ vzroste, tak¾e prùchodù
    bude maximálnì~$n$ a celý algoritmus tak pobì¾í v~èase $\O(n^2m)$.
\endlist

\s{Korektnost algoritmu:}
Kdy¾ se Dinicùv algoritmus zastaví, nemù¾e u¾ existovat ¾ádná zlep¹ující cesta
(viz krok~4) a tehdy, jak u¾ víme z~analýzy F-F algoritmu, je nalezený tok maximální.

\s{Vìta:}
V~ka¾dém prùchodu Dinicova algoritmu vzroste $l$ alespoò~o~1.

\proof
Podíváme se na~prùbìh jednoho prùchodu vnìj¹ím cyklem.
Délku aktuálnì nejkrat¹í $st$-cesty oznaème~$l$.
V¹echny pùvodní cesty délky~$l$ se bìhem prùchodu zaruèenì nasytí, proto¾e
tok~$f_B$ je blokující. Musíme v¹ak dokázat, ¾e nemohou vzniknout ¾ádné
nové cesty délky~$l$ nebo men¹í. V~síti rezerv toti¾ mohou hrany nejen
ubývat, ale i pøibývat: pokud po¹leme tok po~hranì, po~které je¹tì nic
neteklo, tak v~protismìru z~dosud nulové rezervy vyrobíme nenulovou.
Rozmysleme si tedy, jaké hrany mohou pøibývat:

Vnìj¹í cyklus zaèíná s neproèi¹tìnou sítí. Pøíklad takové sítì je na~následujícím obrázku.
Po~proèi¹tìní zùstanou v~síti jen èerné hrany, tedy hrany vedoucí z~$i$-té
vrstvy do~$(i+1)$-ní. Èervené a modré\foot{Modré jsou ty, které vedou v rámci jedné vrstvy,
èervené vedou zpìt èi za~spotøebiè èi do~slepých ulièek. Pøi vyti¹tìní na papír vypadají v¹echny èernì.}
se zahodí.

Nové hrany mohou vznikat výhradnì jako opaèné k~èerným hranám (hrany ostatních barev
padly za obì» proèi¹tìní). Jsou to tedy v¾dy zpìtné hrany vedoucí z~$i$-té vrstvy do~$(i-1)$-ní.
Vznikem nových hran by proto mohly vzniknout nové $st$-cesty, které pou¾ívají
zpìtné hrany. Jen¾e $st$-cesta, která pou¾ije zpìtnou hranu, musí alespoò jednou skoèit
o~vrstvu zpìt a nikdy nemù¾e skoèit o~více ne¾ jednu vrstvu dopøedu, a~proto je její
délka alespoò $l+2$. Tím je vìta dokázána. \qed

% posunut dále, aby vy¹la sazba
\figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a slepé ulièky.}{0.45\hsize}

% HACK
\vskip -10pt

\figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.4\hsize}

\h{Poznámky}

\itemize\ibull
\:Není potøeba tak puntièkáøské èi¹tìní. Vrcholy se vstupním stupnìm 0 nám
   nevadí -- stejnì se do nich nedostaneme. Vadí jen vrcholy s výstupním stupnìm 0, kde by mohl
   havarovat postup v podkroku 9.
\:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e prohledáváním do~hloubky:
   \uv{Hrrr na nì!} a kdy¾
   to nevyjde (dostaneme se do slepé ulièky), kus ustoupíme a pøi ústupu èistíme sí»
   odstraòováním slepé ulièky.
\:U¾ pøi prohledávání si rovnou udr¾ujeme minimum z rezerv a pøi zpáteèní cestì
   opravujeme kapacity. Snadno zkombinujeme s~prohledáváním do~hloubky.
\:V prùbìhu výpoètu udr¾ujeme jen sí» rezerv a tok vypoèteme a¾ nakonec z rezerv a kapacit.
\:Kdy¾ budeme chtít hledat minimální øez, spustíme po~Dinicovu algoritmu je¹tì jednu iterací F-F
   algoritmu.
\endlist

\h{Speciální sítì (ubíráme na obecnosti)}

Pøi pøevodu rùzných úloh na~hledání maximálního toku èasto dostaneme sí» v~nìjakém
speciálním tvaru -- tøeba s~omezenými kapacitami èi stupni vrcholù. Podíváme se
proto podrobnìji na~chování Dinicova algoritmu v~takových pøípadech a uká¾eme,
¾e èasto pracuje pøekvapivì efektivnì.

\s{Jednotkové kapacity:}
Pokud sí» neobsahuje cykly délky~2 (dvojice navzájem opaèných hran), v¹echny rezervy
jsou jen 0 nebo~1. Pokud obsahuje, mohou rezervy být i dvojky, a~proto sí» upravíme tak,
¾e ke~ka¾dé hranì pøidáme hranu opaènou s~nulovou kapacitou a rezervu proti smìru
toku pøiøkneme jí. Vzniknou tím sice paralelní hrany, ale to tokovým algoritmùm
nikterak nevadí.%
\foot{Èasto se to implementuje tak, ¾e protismìrné hrany vùbec nevytvoøíme a kdy¾
hranu nasytíme, tak v~síti rezerv prostì obrátíme její orientaci.}

Pøi hledání blokujícího toku tedy budou mít v¹echny hrany na~nalezené $st$-cestì
stejnou, toti¾ jednotkovou, rezervu, tak¾e v¾dy z~grafu odstraníme celou cestu.
Kdy¾ máme $m$ hran, poèet zlep¹ení po cestách délky $l$ bude maximálnì $m/l$.
Proto slo¾itost podkrokù 9, 10 a 11 bude $m/l \cdot \O(l) = \O(m)$.%
\foot{Nebo by ¹lo argumentovat, tím ¾e ka¾dou hranu pou¾ijeme jen $1\times$.}
Tedy pro jednotkové kapacity dostáváme slo¾itost $\O(nm)$.

\s{Jednotkové kapacity znovu a lépe:}
Vnitøní cyklus lépe udìlat nepùjde. Je potøeba alespoò lineární èas pro èi¹tìní.
Mù¾eme se ale pokusit lépe odhadnout poèet iterací vnìj¹ího cyklu.

Sledujme stav sítì po $k$ iteracích vnìj¹ího cyklu a pokusme se odhadnout, kolik iterací
je¹tì algoritmus udìlá. Oznaème~$l$ délku nejkrat¹í $st$-cesty.
Víme, ¾e $l>k$, proto¾e v ka¾dé iteraci vzroste $l$ alespoò o 1.

Máme tok $f_k$ a chceme dostat maximální tok $f$. Rozdíl $f-f_k$ je tok v~síti rezerv
(tok v~pùvodní síti to ov¹em být nemusí!), oznaème si ho~$f_R$.
Ka¾dá iterace velkého cyklu zlep¹í $f_k$ alespoò o 1. Tedy nám zbývá je¹tì
nejvý¹e $\vert f_R \vert$ iterací.
Proto bychom chtìli omezit velikost toku $f_R$. Napøíklad øezem.

Najdeme v síti rezerv nìjaký dost malý øez $C$. Kde ho vzít?\foot{Pøeci v øeznictví. Kdepak, spí¹e v cukrárnì.
Myslíte, ¾e v cukrárnì mají Dinicovy øezy? Myslím, ¾e v cukrárnì je vìt¹ina øezù minimální. {\sl (odposlechnuto na~pøedná¹ce)}}
Poèítejme jen hrany zleva doprava. Tìch je jistì nejvý¹e $m$ a tvoøí alespoò $k$ rozhraní mezi
vrstvami. Tedy existuje rozhraní vrstev
s~nejvý¹e $m/k$ hranami\foot{Princip holubníku a nìjaká ta $\pm1$.}.
Toto rozhraní je øez. Tedy existuje øez~$C$, pro nìj¾ $\vert C\vert \leq m/k$,
a~algoritmu zbývá maximálnì $m/k$ dal¹ích krokù.
Celkový poèet krokù je nejvý¹ $k + m/k$, tak¾e staèí zvolit $k = \sqrt{m}$ a získáme
odhad na~poèet krokù $\O(\sqrt{m})$.

Tím jsme dokázali, ¾e celková slo¾itost Dinicova algoritmu pro jednotkové
kapacity je $\O(m^{3/2})$. Tím jsme si pomohli pro øídké grafy.

\vbox{
\inlinefig{dinic-vrcholrez.eps}{0.2\hsize}
\s{Jednotkové kapacity a jeden ze stupòù roven 1:}
Úlohu hledání maximálního párování v~bipartitním grafu, pøípadnì hledání
vrcholovì disjunktních cest v~obecném grafu lze pøevést (viz pøedchozí kapitola)
na~hledání maximálního toku v~síti, v~ní¾ má ka¾dý vrchol~$v\ne s,t$ buïto vstupní
nebo výstupní stupeò roven jedné.
Pro takovou sí» mù¾eme pøedchozí odhad je¹tì tro¹ku upravit. Pokusíme
se nalézt v síti po~$k$~krocích nìjaký malý øez. Místo rozhraní budeme hledat jednu malou
vrstvu a z~malé vrstvy vytvoøíme malý øez tak, ¾e pro ka¾dý vrchol z~vrstvy vezmeme tu hranu,
která je ve~svém smìru sama.

}

Po $k$ krocích máme alespoò $k$ vrstev, a~proto existuje vrstva $\delta$ s nejvý¹e $n/k$ vrcholy.
Tedy existuje øez $C$ o~velikosti $\vert C\vert \leq n/k$ (získáme z vrstvy $\delta$ vý¹e popsaným postupem).
Algoritmu zbývá do konce $\leq n/k$ iterací vnìj¹ího cyklu, celkem tedy udìlá $k + n/k$ iterací.
Nyní staèí zvolit $k = \sqrt{n}$ a slo¾itost
celého algoritmu vyjde $\O(\sqrt{n}\cdot m)$.

Mimochodem, hledání maximálního párování pomocí Dinicova algoritmu je také ekvivalentní
známému Hopcroft-Karpovì algoritmu \cite{hopcroft:matching}. Ten je zalo¾en na~støídavých
cestách z~pøedchozí kapitoly a v~ka¾dé iteraci nalezne mno¾inu vrcholovì disjuktních
nejkrat¹ích støidavých cest, která je maximální vzhledem k~inkluzi.
Touto mno¾inou pak aktuální párování pøexoruje, èím¾ ho zvìt¹í. V¹imnìte si, ¾e tyto
mno¾iny cest odpovídají právì blokujícím tokùm v~proèi¹tìné síti rezerv, tak¾e mù¾eme
i~zde pou¾ít ná¹ odhad na~poèet iterací.

\s{Tøetí pokus pro jednotkové kapacity bez omezení na stupnì vrcholù v síti:}
Hlavní my¹lenkou je opìt po $k$ krocích najít nìjaký malý øez. Najdeme dvì malé
sousední vrstvy a v¹echny hrany mezi nimi budou tvoøit námi hledaný malý øez.
Budeme tentokrát pøedpokládat, ¾e na¹e sí» není multigraf, pøípadnì ¾e
násobnost hran je alespoò omezena konstantou.

Oznaème $s_i$ poèet vrcholù v $i$-té vrstvì. Souèet poètu vrcholù ve dvou
sousedních vrstvách oznaèíme $t_i = s_i + s_{i+1}$. Bude tedy platit nerovnost:
$$\sum_i t_i \leq 2\sum_i s_i \leq 2n.$$
Podle holubníkového principu existuje $i$ takové, ¾e $t_i \leq 2n/k$, èili
$s_i + s_{i+1} \leq 2n/k$. Poèet hran mezi $s_i$ a $s_{i+1}$ je velikost øezu
$C$, a to je shora omezeno $s_i \cdot s_{i+1}$. Nejhor¹í pøípad nastane, kdy¾ $s_i = s_{i+1} = n/k$,
a~proto $\vert C\vert \leq {(n/k)}^2$.
Proto poèet iterací velkého cyklu je $\leq k + {(n/k)}^2$.
Chytøe zvolíme $k = n^{2/3}$. Slo¾itost celého algoritmu pak bude $\O(n^{2/3}m)$.

\s{Obecný odhad pro celoèíselné kapacity:}
Tento odhad je zalo¾en na velikosti
maximálního toku $f$ a pøedpokladu celoèíselných kapacit.
Za jednu iteraci velkého cyklu projdeme malým cyklem maximálnì tolikrát,
o kolik se v nìm zvedl tok, proto¾e ka¾dá zlep¹ující cesta ho zvedne alespoò o $1$.
Zlep¹ující cesta se tedy hledá maximálnì  $\vert f\vert$-krát za celou dobu bìhu algoritmu.
Cestu najdeme v èase $\O(n)$. Celkem na~hledání
cest spotøebujeme $\O(\vert f\vert\cdot n)$ za celou dobu bìhu algoritmu.

Nesmíme ale zapomenout na èi¹tìní. V jedné iteraci velkého cyklu nás stojí èi¹tìní $\O(m)$ a velkých
iterací je $\leq n$. Proto celková slo¾itost algoritmu èiní $\O(\vert f\vert n + nm)$

Pokud navíc budeme pøedpokládat, ¾e kapacita hran je nejvý¹e~$C$ a $G$ není multigraf,
mù¾eme vyu¾ít toho, ¾e $\vert f\vert \le Cn$ (omezeno øezem okolo~$s$) a získat odhad
$\O(Cn^2 + nm)$.

\h{©kálování kapacit}

Pokud jsou kapacity hran vìt¹í celá èísla omezená nìjakou konstantou~$C$, mù¾eme si pomoci následujícím algoritmem.
Jeho základní my¹lenka je podobná, jako u~tøídìní èísel postupnì po øádech pomocí
radix-sortu neboli pøihrádkového tøídìní. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední
(nejménì významné) cifry, poté podle pøedposlední, pøedpøedposlední a tak dále.

%\figure{dinic-sort.eps}{Kroky postupného tøídìní podle øádù}{0.4\hsize}

V na¹em pøípadì budeme postupnì budovat sítì èím dál podobnìj¹í zadané
síti a v~nich poèítat toky, a¾ nakonec získáme tok pro ni.

Pøesnìji: Maximální tok v síti $G$ budeme hledat tak, ¾e hranám postupnì
budeme zvìt¹ovat kapacity bit po bitu v~binárním zápisu a¾ k~jejich skuteèné kapacitì.
Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus, aby dopoèítal maximální tok.
Pomocí pøedchozího odhadu uká¾eme, ¾e jeden takový krok nebude pøíli¹ drahý.

\figure{dinic-scaling-original.eps}{Pùvodní sí», na hranách jsou jejich kapacity v binárním zápisu}{0.3\hsize}

Oznaème $k$ index nejvy¹¹ího bitu v~zápisu kapacit v~zadané síti ($k = \lfloor \log_2C \rfloor$).
Postupnì budeme budovat sítì $G_i$ s~kapacitami $c_i(e) = \lfloor {c(e) / 2^{k-i}} \rfloor$.
$G_0$ je nejoøezanìj¹í sí», kde ka¾dá hrana má kapacitu rovnou nejvy¹¹ímu bitu v~binárním zápisu
její skuteèné kapacity, a¾ $G_k$ je pùvodní sí» $G$.

\figure{dinic-scaling-g.eps}{Sítì $G_0$, $G_1$ a $G_2$, jak vyjdou pro sí» z~pøedchozího obrázku}{0.9\hsize}

\>Pøitom pro kapacity v~jednotlivých sítích platí:

$$ c_{i+1}(e) = \left\{
\eqalign{
           2c_i(e),   &\hbox{\quad pokud $(k-i-1)$-tý bit je 0,}  \cr
           2c_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bit je 1.}  \cr}
\right.
$$

Na spoètení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicùv algoritmus,
ov¹em do zaèátku nepou¾ijeme nulový tok, nýbr¾ tok $2f_{i-1}$. Rozdíl toku z inicializace
a výsledného bude malý, toti¾:

\s{Lemma:} $\vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$

\proof
Vezmeme minimální øez $R$ v~$G_{i-1}$. Podle F-F vìty víme, ¾e $\vert f_{i-1}\vert = \vert R\vert$.
Øez $R$ obsahuje $\leq m$ hran, a~tedy v~$G_{i}$ má tentý¾ øez kapacitu maximálnì $2\vert R\vert+m$.
Maximální tok je omezen ka¾dým øezem, tedy i øezem $R$, a~proto tok vzroste nejvý¹e o~$m$.
\qed

Podle pøedchozího odhadu pro celoèíselné kapacity výpoèet toku $f_i$ trvá $\O(mn)$.
Takový tok se bude poèítat $k$-krát, proèe¾ celková slo¾itost vyjde $\O(mn\log C)$.

\h{Algoritmus tøí Indù}

Pøekvapení na~konec: Dinicùv algoritmus lze pomìrnì snadno zrychlit i ve~zcela obecném
pøípadì. Malhotra, Kumar a Maheshwari vymysleli efektivnìj¹í algoritmus \cite{threeinds}
na~hledání blokujícího toku ve~vrstevnaté síti, který bì¾í v~èase $\O(n^2)$ a pou¾ijeme-li
ho v~Dinicovì algoritmu, zrychlíme hledání maximálního toku na~$\O(n^3)$.
Tento algoritmus ve¹el do~dìjin pod názvem Metoda tøí Indù.

Mìjme tedy nìjakou vrstevnatou sí». Zaèneme s~nulovým tokem a budeme ho postupnì zlep¹ovat.
Prùbì¾nì si budeme udr¾ovat rezervy hran~$r(e)$\foot{poèítáme pouze rezervu ve~smìru hrany, nebo»
nám staèí najít blokující tok, ne~nutnì maximální} a také následující rezervy vrcholù:

\s{Definice:} $r^+(v)$ je souèet rezerv v¹ech hran vstupujících do~$v$, $r^-(v)$ souèet
rezerv hran vystupujících z~$v$ a koneènì $r(v):=\min(r^+(v),r^-(v))$.

V~ka¾dé iteraci algoritmu nalezneme vrchol s~nejni¾¹ím~$r(v)$ a zvìt¹íme tok tak, aby se
tato rezerva vynulovala. Za~tímto úèelem nejdøíve pøepravíme $r(v)$ jednotek toku ze~zdroje
do~$v$: u~ka¾dého vrcholu~$w$ si budeme pamatovat {\I plán} $p(w)$, co¾ bude mno¾ství
tekutiny, které potøebujeme dostat ze~zdroje do~$w$. Nejdøíve budou plány v¹ude nulové
a¾ na~$p(v)=r(v)$. Pak budeme postupovat po~vrstvách smìrem ke~zdroji a plány v¹ech
vrcholù splníme tak, ¾e je pøevedeme na~plány vrcholù v~následující vrstvì, a¾ doputujeme
ke~zdroji, jeho¾ plán je splnìn triviálnì. Nakonec analogickým zpùsobem protlaèíme $r(v)$
jednotek z~$v$ do~spotøebièe.

Bìhem výpoètu prùbì¾nì pøepoèítáváme v¹echna $r^+$, $r^-$ a~$r$ podle toho, jak se mìní
rezervy jednotlivých hran (pøi ka¾dé úpravì rezervy to zvládneme v~konstantním èase)
a sí» èistíme stejnì jako u~Dinicova algoritmu.

\finalfix{\goodbreak}

\s{Algoritmus:} (hledání blokujícího toku ve~vrstevnaté síti podle tøí Indù)

\algo
\:$f_B\leftarrow\<prázdný tok>$.
\:Spoèítáme rezervy v¹ech hran a $r^+$, $r^-$ a $r$ v¹ech vrcholù. (Tyto hodnoty
  budeme posléze udr¾ovat pøi ka¾dé zmìnì toku po~hranì.)
\:Dokud v~síti existují vrcholy s~nenulovou rezervou, vezmeme vrchol $v$ s~nejmen¹ím $r(v)$
  a provedeme pro nìj: {\I (vnìj¹í cyklus)}
\::Pøevedeme $r(v)$ jednotek toku z~$s$ do~$v$ následovnì:
\:::Polo¾íme $p(v)\leftarrow r(v)$, $p(\cdot)=0$.
\:::Procházíme vrcholy sítì po~vrstvách od~$v$ smìrem k~$s$. Pro ka¾dý vrchol~$w$ provedeme:
\::::Dokud $p(w)>0$:
\:::::Vezmeme libovolnou hranu $uw$ a tok po~ní zvý¹íme o~$\delta=\min(r(uw), p(w))$. Tím se
      $p(w)$ sní¾í~o~$\delta$ a $p(u)$ zvý¹í~o~$\delta$.
\:::::Pokud se hrana~$uw$ nasytila, odstraníme jí ze sítì a sí» doèistíme.
\::Analogicky pøevedeme $r(v)$ jednotek z~$v$ do~$t$.
\endalgo

\s{Analýza:} Nejprve si v¹imneme, ¾e cyklus v~kroku~8 opravdu doká¾e vynulovat $p(w)$.
Souèet v¹ech $p(w)$ pøes ka¾dou vrstvu je toti¾ nejvý¹e roven $r(v)$, tak¾e speciálnì ka¾dé
$p(w)\le r(v)$. Jen¾e $r(v)$ jsme vybrali jako nejmen¹í, tak¾e $p(w)\le r(v)\le r(w)\le r^+(w)$,
a~proto je plánovaný tok kudy pøivést. Proto se algoritmus zastaví a vydá blokující tok.

Zbývá odhadnout èasovou slo¾itost: Kdy¾ oddìlíme pøevádìní plánù po~hranách (kroky 7--9),
zbytek jedné iterace vnìj¹ího cyklu trvá~$\O(n)$ a tìchto iterací je nejvý¹e~$n$. V¹echna pøevedení
plánu si rozdìlíme na~ta, kterými se nìjaká hrana nasytila, a~ta, která skonèila vynulováním $p(w)$.
Tìch prvních je $\O(m)$, proto¾e ka¾dou takovou hranu vzápìtí odstraníme a èi¹tìní, jak u¾ víme,
trvá také lineárnì dlouho. Druhý pøípad nastane pro ka¾dý vrchol nejvý¹e jednou za~iteraci.
Dohromady tedy trvají v¹echna pøevedení $\O(n^2)$, stejnì jako zbytek algoritmu.
\qed

\h{Pøehled variant Dinicova algoritmu}

\medskip

\centerline{\vbox{\halign{# \hfil \quad &# \hfil \cr
\it varianta &\it èas \cr\noalign{\smallskip\hrule\smallskip}
standardní                              &$\O(n^2m)$      \cr
jednotkové kapacity                     &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$   \cr
jednotkové kapacity, 1 stupeò $\leq 1$  &$\O(\sqrt{n}\cdot m)$   \cr
jednotkové kapacity, prostý graf        &$\O(n^{2/3}m)$    \cr
celoèíselné kapacity                    &$\O(\vert f\vert\cdot n + nm)$     \cr
celoèíselné kapacity $ \leq C$          &$\O(Cn^2 + mn)$   \cr
celoèíselné kapacity $ \leq C$ (¹kálování)&$\O(mn\log C)$    \cr
tøi Indové                              &$\O(n^3)$         \cr
}}}

\references

\bye