Cesko.wiki Dinicův algoritmus
Author
Albert FloresDiniců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ů. +more # 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ů.
| px" | G | G_f | G_L |
|---|---|---|---|
| 1. | +moresvg'>300px | 300px | 300px |
| 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. | 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. | 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. | 300px | 300px | 300px |
| 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. | 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. | 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. | 300px | 300px | 300px |
| 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. | 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. | 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(n m) * 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).
Související články
Tok v síti * Goldbergův algoritmus * Fordův-Fulkersonův algoritmus
Reference
Jakub Černý: [url=https://web. archive. +moreorg/web/20071018060717/http://kam. mff. cuni. cz/~kuba/ka/]Základní grafové algoritmy[/url] (texty v pdf) * Martin Mareš, Tomáš Valla: [url=https://knihy. nic. cz/files/edice/pruvodce_labyrintem_algoritmu. pdf]Průvodce labyrintem algoritmů[/url] (text v pdf).