Algoritmus nejhořejší cesty

Technology
12 hours ago
8
4
2
Avatar
Author
Albert Flores

Algoritmus nejhořejší cesty (Uppermost Path Algorithm) počítá maximální tok v neorientované síti, která odpovídá rovinnému grafu. Zároveň musí být splněno, že zdroj i stok leží ve vnější stěně.

Princip algoritmu

Jedná se, jak název napovídá, o algoritmus založený na hledání zlepšující cesty. Na rozdíl od algoritmu Fordově-Fulkersonově a odvozeným je ale hledání zlepšující cesty výrazně jednodušší. +more Algoritmus se provádí nad nějakým nakreslením sítě. Jako zlepšující cestu vyberu vždy nejhořejší nenasycenou cestu ze zdroje do stoku - tj. nakreslím-li zdroj vlevo a stok vpravo, v každém vrcholu vybírám nejlevější použitelnou hranu (při nalezené slepé uličky se vrátím pomocí backtrackingu a slepou uličku označím jako nepoužitelnou). Poté zvýším tok touto cestou na maximum. Alespoň jedna hrana se tím nasytí a stane se nepoužitelnou. Takto postupuji, dokud existuje cesta ze zdroje do stoku. Výsledkem je nalezení maximálního toku.

Dualita s Dijkstrovým algoritmem

Lze učinit pozorování, že tento algoritmus je duální k Dijkstrovu algoritmu. Pokud totiž vnější stěnu rozdělíme na dolní a horní polorovinu, k nakreslení sítě najdeme duální nakreslení a hranám jako délku přiřadíme jejich kapacitu, nejkratší cesta nalezená Dijkstrovým algoritmem tvoří minimální řez; tok hranou je rozdíl mezi vzdálenostmi jejích vrcholů od horní poloroviny.

Kategorie:Grafové algoritmy Kategorie:Vyhledávací algoritmy

5 min read
Share this post:
Like it 8

Leave a Comment

Please, enter your name.
Please, provide a valid email address.
Please, enter your comment.
Enjoy this post? Join Cesko.wiki
Don’t forget to share it
Top