Dinicův algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
m oprava překlepů: přibydou → přibudou, zbyde → zbude; kosmetické úpravy |
Mírné rozšíření článků, přidání příkladu z anglické wikipedie, přidání reference značka: přepnuto z Vizuálního editoru |
||
Řádek 1:
'''Dinicův algoritmus''' (1970) je algoritmus vyvinutý Jefim Dinicem pro výpočet [[maximální tok|maximálního toku]] v [[Síť (teorie grafů)|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 tak maximální. Tento přístup dovoluje v průměrném případě počítat maximální tok rychleji než [[Fordův–Fulkersonův algoritmus|Ford–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 ''
# 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)
Řádek 9:
#: 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 ''
# zjistím minimum ''m'' z rezerv na této cestě, zvýším o ''m'' tok podél celé cesty, čímž do sítě rezerv přibudou zpětné hrany s rezervou ''m'', a u jedné hrany v cestě zmizí dopředná hrana
# vyčistím síť, a pokud zbude nějaká cesta z ''
# 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 ''
== Příklad ==
Následující příklad ilustruju průběh Dinicova algoritmu. <math>G</math> představuje aktuální stav grafu,<math>G_f</math> síť rezerv a <math>G_L</math> nalezený blokující tok. Červené hodnoty v jednotlivých vrcholem reprezentují vzdálenost bodů od zdroje (<math>\operatorname{dist}(v)</math>).
{| class="wikitable" style="text-align:center; width:915px;" border="1"
|-
! width="15px" |
! <math>G</math>
! <math>G_f</math>
! <math>G_L</math>
|-
! 1.
| [[File:Dinic algorithm G1.svg|300px]]
| [[File:Dinic algorithm Gf1.svg|300px]]
| [[File:Dinic algorithm GL1.svg|300px]]
|-
|
| align="left" colspan="3" |
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:
# <math>\{s, 1, 3, t\}</math> se 4 jednotkami toku,
# <math>\{s, 1, 4, t\}</math> s 6 jednotkami toku,
# <math>\{s, 2, 4, t\}</math> se 4 jednotkami toku.
Celkově má blokující tok velikost 14 jednotek.
|-
! 2.
| [[File:Dinic algorithm G2.svg|300px]]
| [[File:Dinic algorithm Gf2.svg|300px]]
| [[File:Dinic algorithm GL2.svg|300px]]
|-
|
| align="left" colspan="3" |
Do <math>G</math> připočteme blokující tok nalezený v předchozí iteraci. Do <math>G_f</math> 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:
# <math>\{s, 2, 4, 3, t\}</math> s 5 jednotkami.
K celému toku připočteme blokující tj. <math>|f|</math> is 14 + 5 = 19.
|-
! 3.
| [[File:Dinic algorithm G3.svg|300px]]
| [[File:Dinic algorithm Gf3.svg|300px]]
| [[File:Dinic algorithm GL3.svg|300px]]
|-
|
| align="left" colspan="3" |
Blokující tok opět připočteme do původního grafu <math>G</math> a upravíme i hodnoty v grafu rezerv (<math>G_f</math>).
V tuto chvíli již neexistuje žádná cesta ze zdroje do stoku (<math>t</math>), tedy algoritmus vrátí maximální tok <math>|f|</math> = 19.
|-
|}
== Složitost algoritmu ==
[[Asymptotická časová složitost]] algoritmu je <math>O(n^2 m)</math>, kde ''n'' označuje počet [[Graf (teorie grafů)#Základní pojmy|vrcholů]] a ''m'' počet [[Hrana (graf)|hran]] zpracovávaného grafu. Pokud chceme vyjádřit složitost pouze v závislosti na ''n'', je tato <math>O(n^4)</math>, neboť hran grafu je řádově nejvýše <math>n^2</math>.
Řádek 31 ⟶ 82:
== Reference ==
* Jakub Černý: [http://kam.mff.cuni.cz/~kuba/ka/ Základní grafové algoritmy] (texty v pdf)
* Martin Mareš, Tomáš Valla: [https://knihy.nic.cz/files/edice/Pruvodce_labyrintem_algoritmu.pdf Průvodce labyrintem algoritmů] (text v pdf)
[[Kategorie:Toky v sítích]]
| |||