Cesko.wiki Algoritmus nejhořejší cesty
Author
Albert FloresAlgoritmus 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.