Na čistou síť $G^*_f$ s rezervami se můžeme dívat jako na obyčejnou síť s kapacitami (kapacitou každé hrany je velikost rezervy) a můžeme v ní hledat tok. Graf čisté sítě je acyklický orientovaný graf.

Tok $\phi$ v acyklické orientované síti je blokující tok, pokud je každá orientovaná $(s,t)$-cesta v $G^*_f$ nasycená. Důležité je slovo orientovaná. Cesta obsahující hranu v protisměru není přípustná. Blokující tok nemusí být maximální tok, protože může existovat vylepšující cesta používající hrany v protisměru.

Blokující tok můžeme najít pomocí vylepšujících cest, které nevyužívají rezervy v protisměru. Blokující tok $\phi$ v čisté síti $G^*_f$ je roven toku, o který zvětšíme $f$ během jedné fáze Dinicova algoritmu, tj. při vylepšování toku $f$ podél vylepšujících cest stejné délky.

Dinic:

	 zvol počáteční tok, například $f:=0$
	 repeat 
	 	 spočítej síť rezerv
	 	 spočítej čistou síť
	 	 nalezni blokující tok v čisté síti a přičti ho k $f$
	 until spočítaná čistá síť obsahovala hrany 
	 return $f$ 

Když nově spočítaná čistá síť neobsahuje hrany, tak můžeme skončit, protože neexistuje cesta ze zdroje do spotřebiče v $G_f$, tedy ani žádná vylepšující cesta v $G$. V ten moment máme maximální tok.

Repeat-cyklus proběhne nejvýše $n$-krát, protože v každé iteraci se zvětší délka nejkratší vylepšující cesty. Provedení kroků $4$ a $5$ bude trvat čas $\OO(n+m)$, protože oba kroky provedeme pomocí průchodu grafu. Jak se provede krok $6$ si ukážeme za chvilku. Ukážeme, že krok $6$ trvá čas $\OO(nm)$. Dohromady dostaneme časovou složitost Dinicova algoritmu $\OO(n^2m)$.

nalezení blokujícího toku v čisté síti:

	 while čistá síť obsahuje hrany do
	 	 najdi v čisté síti cestu ze zdroje do spotřebiče
	 	 spočítej hodnotu nejmenší rezervy na cestě
	 	 vylepši tok $f$ podél cesty a uprav čistou síť
	 	 dočisti čistou síť

Krok $3$ provedeme hladově například průchodem do hloubky. Při návratu v průchodu do hloubky můžeme rovnou počítat krok $4$. Proto budou oba kroky trvat čas $\OO(n)$. Stejně tak vylepšení toku podél nalezené cesty.

Jak budeme upravovat a dočisťovat čistou síť? Pro každý vrchol si budeme pamatovat jeho vstupní a výstupní stupeň. Vylepšením toku klesne rezerva některých hran na nulu. Takové hrany musíme z čisté sítě vymazat. Musíme si ale dát pozor, aby nám vymazáním některých hran nevznikly slepé uličky. To jsou cesty vedoucí do vrcholů, ze kterých už nejde pokračovat dál. Proto při vymazávaní každé hrany vložíme její konce do fronty. Při dočišťování čisté sítě postupně probíráme vrcholy ve frontě a pokud mají vstupní nebo výstupní stupeň nula, tak vymažeme všechny hrany z nich vedoucí. Druhé konce mazaných hran vkládáme opět do fronty a při tom aktualizujeme vstupní a výstupní stupně těchto vrcholů. Po zpracování fronty dostaneme korektní čistou síť, ve které můžeme znova začít hledat vylepšující cestu.

Čas za zpracování fronty budeme účtovat jednotlivým hranám. Každý vrchol, který byl vložen do fronty, odpovídá jedné smazané hraně. Hrana mohla do fronty vložit nejvýše své dva koncové vrcholy. Z toho vyplývá, že časová složitost všech provedení kroků $6$ je $\OO(m)$. While-cyklus proběhne nejvýše $m$-krát, protože pokaždé vymažeme alespoň jednu hranu čisté sítě. Celková časová složitost nalezení blokujícího toku v čisté síti je $\OO(mn)$.


Poznámky k implementaci

Ve skutečnosti nepotřebujeme rozlišovat mezi sítí rezerv a čistou sítí. V iteraci nám stačí jen jedna síť. Nejprve spočítáme síť rezerv. V té provedeme průchod do šířky, během kterého umazáváme hrany neležící na nejkratší cestě ze zdroje do spotřebiče. Nechť $S$ je množina vrcholů ležících na nějaké nejkratší cestě ze zdroje do spotřebiče. Výpočet čisté sítě provedeme následovně. Na začátku je $S=\{t\}$. Síť rezerv procházíme do šířky a při každém návratu po hraně $uv$ hranu smažeme, pokud $v\not\in S$, jinak přidáme $u$ do $S$ a hranu necháme v čisté síti. Tím dostaneme čistou síť.

Také není potřeba provádět dokonalé dočišťování čisté sítě. Do vrcholů, do kterých nevede žádná cesta, se nemáme jak dostat. Proto takové vrcholy a cesty z nich vedoucí můžeme v síti nechat.

Odstraňování vrcholů na slepých uličkách, ze kterých nevede cesta dál, můžeme provést podobným trikem, jako při hledání čisté sítě. Čistou sít nebudeme dočišťovat v kroku $6$, ale až v kroku $3$ při dalším průběhu cyklu. V kroku $3$ hledáme cestu ze zdroje do spotřebiče v čisté síti. Hledání provedeme pomocí průchodu do hloubky. Pokud bychom při průchodu do hloubky přešli po hraně $uv$ takové, že z $v$ nelze pokračovat dál, tak při návratu hranu $uv$ smažeme. Mazání naúčtujeme mazaným hranám.

Ve speciálních sítích má Dinicův algoritmus ještě lepší časovou složitost. O tom se ale dozvíte více ve cvičeních. Zájemce také můžeme odkázat na Schrijvera [SCombOpt] nebo Mareše [MaresKGA].