PROFILPELAJAR.COM

Dinicův algoritmus je algoritmus vyvinutý Jefimem Dinicem (1970) pro výpočet maximálního toku v síti. Hlavní myšlenka algoritmu spočívá v iterativním výpočtu tzv. "blokujících" toků, které se postupně nasčítají až na tok maximální. Tento přístup dovoluje v průměrném případě počítat maximální tok rychleji než Fordovým–Fulkersonovým algoritmem, který pro výpočet využívá hledání zlepšujících cest.

Algoritmus

vyrobím síť rezerv
projdu graf z s (zdroje) do šířky a zjistím délku d nejkratší cesty do t (stoku)
vyhodím
hrany začínající a končící ve stejné vrstvě nebo hrany nazpátek (ty nepoužijeme—nejkratší cesta jimi jít nemůže)

a také vrcholy, které tvoří "slepé uličky" (nevede z nich žádná dopředná hrana)

a hrany do těchto vrcholů (cyklicky—odstraněním konce slepé uličky může vzniknout nový konec)
výsledek kroku 3 nazvu "čistá síť"
najdu cestu z s do t délky d
spočítám m z toku a rezerv tak, že se sečte vstupní toky do uzlu a rozdělí se dle volných kapacit na výstupní hrany.
zjistím minimum m zpětným průchodem cesty a snížím vstupní toky na využitelnou kapacitu výstupního toku tak, aby platilo že součet vstupů se rovná součtu výstupů.
zjištěné minimum m přičtu k dosud nalezeným tokům v síti a síť rezerv upravíme tak, že
nalezené toky zaneseme do grafu jako zpětné hrany, případně navýším existující a

od dopředných hran kapacit odečtu nalezené toky.

pokud je kapacita nulová, pak šipku z grafu odstraním.
vyčistím síť, a pokud zbude nějaká cesta z s do t délky d, jdu na krok 5
vezmu celou síť a jdu na 2 (nejkratší cesta bude mít délku d+1, ty kratší už v síti rezerv nejsou)
pokud už neexistuje cesta z s do t, skončil jsem (můžu najít i hrany minimálního řezu—jejich počáteční vrcholy jsou konci slepých uliček)

Příklad

Následující příklad ilustruje průběh Dinicova algoritmu.
$G$ představuje aktuální stav grafu (hrany jsou ohodnoceny nalezeným tokem / kapacitou hrany),
$G_{f}$ síť rezerv (hodnoty hran představují kapacitu hrany; směr šipek ukazuje použitelný/použitý toku)
$G_{L}$ nalezený blokující tok (hrany jsou ohodnoceny nově nalezeným tokem m / zbývající kapacita pro aktuální iteraci - hodnoty zůstavších hran z grafu $G_{f}$ ).
Červené hodnoty ve vrcholem $G_{L}$ reprezentují vzdálenost bodů od zdroje ( $\operatorname {dist} (v)$ ), v ostatních grafech očíslování vrcholů.

	$G$	$G_{f}$	$G_{L}$
1.
	Nejkratší cesta ze zdroje do stoku má délku 3, blokojící tok sestává z následujících zlepšujících cest cest: $\{s,1,3,t\}$ se 4 jednotkami toku, $\{s,1,4,t\}$ s 6 jednotkami toku, $\{s,2,4,t\}$ se 4 jednotkami toku. Celkově má blokující tok velikost 14 jednotek.
2.
	Do $G$ připočteme blokující tok nalezený v předchozí iteraci. Do $G_{f}$ přidáme "protisměrné" hrany reprezentující rezervy hran v protisměru. Opět nalezneme všechny nejkratší zlepšující cesty (v tomto případě cesty délky 4) a "hladově" nalezneme blokující tok. Ten bude obsahovat pouze následující cestu: $\{s,2,4,3,t\}$ s 5 jednotkami. K celému toku připočteme blokující tj. $\|f\|$ is 14 + 5 = 19.
3.
	Blokující tok opět připočteme do původního grafu $G$ a upravíme i hodnoty v grafu rezerv ( $G_{f}$ ). V tuto chvíli již neexistuje žádná cesta ze zdroje do stoku ( $t$ ), tedy algoritmus vrátí maximální tok $\|f\|$ = 19.

Složitost algoritmu

Asymptotická časová složitost algoritmu je $O(n^{2}m)$ , kde n označuje počet vrcholů a m počet hran zpracovávaného grafu. Pokud chceme vyjádřit složitost pouze v závislosti na n, je tato $O(n^{4})$ , neboť hran grafu je řádově nejvýše $n^{2}$ .

Algoritmus lze rozdělit na fáze, kde jednou fází se rozumí jedna posloupnost kroků 2–7. O fázích platí:

každá fáze probíhá s asymptotickou časovou složitostí $O(nm)$
v každé fázi hledáme cesty ze zdroje do spotřebiče délky d, což je délka nejkratší nezpracované cesty v grafu; d je alespoň o 1 větší než d předchozí fáze
fází proběhne nejvýše n

Algoritmus se dá modifikovat takzvanou metodou tří Indů: místo hledání cesty se pro každý vrchol spočítá, jaké mají rezervy vstupní hrany a výstupní hrany jednotlivých vrcholů a vrcholem s nejmenším minimem těchto hodnot se tok zvýší. Tím se asymptotická složitost zlepší na $O(n^{3})$ .

S použitím datových struktur (dynamické stromy) je možno nalézt blokující tok ve vrstevnaté síti v čase $O(m\log n)$ , čímž dostáváme složitost celého algoritmu $O(mn\log n)$ .