Problém nejkratší cesty

Nejkratší cesta

Problém nejkratší cesty je NP-úplná grafová úloha, jejímž cílem je nalézt v zadaném grafu nejkratší cestu mezi uzly a . Rozhodovací varianta úlohy pak odpovídá na otázku, zda-li v daném grafu existuje mezi body a cesta délky maximálně .

Problém nejdelší cesty

Velmi podobným problémem je úloha nalezení nejdelší cesty, jejímž cílem je nalézt mezi body a cestu nejvyšší délky. Vzájemný převod těchto úloh je triviální – stačí otočit znaménka vah všech hran zadaného grafu.

Polynomiální řešení úlohy nejkratší cesty

Základním problémem řešení tohoto problému v polynomiálním čase je možnost existence cyklů záporné délky. Cykly záporné znemožňují efektivně rozhodnout, zda-li již pro daný uzel byla nalezena nejkratší cesta.

Pokud však úloha neobsahuje cykly záporné délky, tak ji lze rozhodnout v polynomiálním čase za pomoci mnoha různých algoritmů. Tyto algoritmy mají společnou jednu vlastnost – ve skutečnosti nehledají nejkratší cestu, ale nejkratší sled (tj. nekontrolují, zda-li daná hrana již nebyla použita). Jelikož ale graf neobsahuje cykly záporné délky, tak je nejkratší sled zároveň také nejkratší cestou.

Další pozitivní skutečností je, že značná část úloh reálného světa cykly záporné délky vůbec neobsahuje. Pokud hledáme nejkratší cestu na mapě, tak jsou vzdálenosti vždy kladné. Pokud bychom stavěli vodovod a zohledňovali jako cenu klesání a stoupání trubek (klesání – voda teče dolů sama (záporná cena), stoupání – musíme koupit čerpadlo (kladná cena)), tak je opět zřejmé, že k cyklu záporné délky nemůže opět nikdy dojít.

Bellmanova rovnice

Polynomiální řešení problému nejkratších (nejdelších) cest je založeno na Bellmanovu principu optimality, který říká, že pokud graf neobsahuje cyklus záporné délky, tak pro každé tři vrcholy , , platí:

$u(x,\\; y) = \\min_{x \\neq y} (u(x,\\; z) + a(z,\\; y))$

Kde $u(x,\\; y)$ značí délku cesty z vrcholu do vrcholu a $a(z,\\; y)$ značí vzálenost vrcholu od vrcholu (tj. délku nejkratší hrany, která tyto vrcholy spojuje).

Z Bellmanovy rovnice jednoduše řečeno vyplývá, že se každá nejkratší cesta skládá z nejkratších cest – tj. nejkratší cesta $[a, \\cdots ,\\; x, \\cdots ,\\; c]$ mezi uzly a obsahuje také nejkratší cestu mezi uzly , a , .

Polynomiální algoritmy

Dijkstrův algoritmus

Nejefektivnějším algoritmem pro hledání nejkratší cesty z uzlu do všech zbylých uzlů grafu je Dijkstrův algoritmus se složitostí $O(\\vert H \\vert \\cdot \\log_{2}(\\vert U \\vert))$ . Dijkstrův algoritmus má ale další dodatečné omezení – nesmí být použit na grafu, který obsahuje jakoukoliv hranu záporné délky.

Bellman-Fordův algoritmus

Bellman-Fordův algoritmus také hledá nejkratší cestu z uzlu do všech zbylých uzlů grafu. Jeho složitost je horší než u Dijkstrova algoritmu – $O(\\vert H\\vert \\cdot \\vert U\\vert)$ , nevadí mu však přítomnost hran záporné délky. Další významnou výhodou pak je detekce cyklů záporné délky – pokud graf obsahuje takovýto cyklus, tak algoritmus cíleně havaruje.

Floyd-Warshallův algoritmus

Floyd-Warshallův algoritmus slouží k nalezení nejkratších cest mezi všemi dvojicemi uzlů. Asymptotická složitost algoritmu je $O(\\vert U \\vert ^{3})$ . Mezi výhody tohoto algoritmu patří především jeho implementační nenáročnost (jedná se o 3 vnořené smyčky) a flexibilita (umožňuje řešení široké škály problémů).