P-III-4 Tunely

První cást úlohy vyresíme pomocí Dijkstrova algoritmu. Postupne budeme
procházet mesty dostupnými z výchozího mesta X, poradí procházení bude
rízeno prubezne pocítanými hodnotami H, které jsou prirazovány
jednotlivým mestum. U kazdého mesta evidujeme maximální výsku vozidla,
jaké se do mesta muze dostat. Pro kazdé mesto navíc rozlisujeme, zda je
jemu prirazená hodnota H docasná (mozná se jeste zmení, tj. vylepsí),
nebo zda je jiz trvalá (urcuje výslednou maximální výsku vozidla, jaké
muze dojet do tohoto mesta).

Pred zahájením pruchodu bude mít výchozí mesto X prirazenu docasnou
hodnotu "nekonecno" (dostane se do nej vozidlo libovolné výsky) a
vsechna ostatní mesta mají docasnou hodnotu 0 (zatím do nich neznáme
zádné cesty). Celý výpocet pak bude probíhat po krocích tak dlouho,
dokud nebude cílovému mestu Y stanovena trvalá hodnota, popr. dokud
nebude prirazena trvalá hodnota vsem dostupným vrcholum a Y mezi nimi
nebude (pak není mesto Y z mesta X vubec dostupné). V kazdém kroku
výpoctu se provedou tyto akce:

   1. Urcíme mesto s maximální docasnou hodnotou H.
   2. Docasnou hodnotu tohoto mesta prohlásíme za trvalou.
   3. Vsem jeho bezprostredním sousedum, kterí mají jeste docasnou
      hodnotu, prepocítáme jejich hodnoty H (viz program). Zvýsíme tím
      vsechny ty docasné hodnoty mest, které je mozné zvýsit díky ceste
      vedoucí pres práve vybrané mesto.

Výsledkem Dijkstrova algoritmu bude urcení maximální výsky vozidla V,
jaké muze projet z mesta X do mesta Y, príp. zjistení, ze tato mesta
nejsou vubec spojena silnicemi.

K vyresení druhé cásti úlohy, tj. nalezení takové cesty vozidlem výsky V
z X do Y, aby vedla pres minimální pocet mest, pouzijeme pruchod do
sírky. Pri procházení pritom budeme uvazovat pouze ty silnice, na nichz
není zádné omezení na výsku vozidla nebo na kterých omezení dovoluje
projet vozidlu výsky V. Z technických duvodu je výhodnejsí provádet
pruchod do sírky "pozpátku" od cílového mesta Y k výchozímu mestu X. Pri
záverecném zpetném chodu pak totiz budem moci prímo vypisovat trasu
vozidla z X do Y, jinak bychom ji jeste museli prevracet.

Pruchod do sírky je rízen pomocnou frontou, v níz jsou v kazdém okamziku
ulozena císla tech mest, do kterých jsme jiz dosli, ale z nichz jsme
jeste nepokracovali v ceste dál. V druhém poli si musíme evidovat jiz
navstívená mesta (abychom do nich nechodili opakovane) a ve tretím poli
si ke kazdému mestu zaznamenáme, odkud jsem do nej poprvé prisli (jeho
predchudce pri pruchodu). Procházení do sírky provádíme tak dlouho,
dokud nedojdeme do mesta X.

Výslednou trasu získáme na záver procházení do sírky zpetným chodem. U
výchozího mesta X je zaznamenán jeho predchudce pri provedeném pruchodu
do sírky, coz je vlastne jeho následník na hledané trase vozidla z X do
Y, u nej je zaznamenán zase jeho predchudce, atd., az se po
zaznamenaných predchudcích dostaneme do cílového mesta Y.

Uvedený postup je jiste konecný. V Dijkstrove algoritmu je v kazdém
kroku jednomu vrcholu prirazena trvalá hodnota. Výpocet tedy skoncí
nejvýse po N krocích, kde N je pocet mest. V kazdém kroku se musí
vyhledat mesto s maximální docasnou hodnotou, coz je výber z N mest.
Provede se pri tom tudíz priblizne N operací. Dále se prepocítávají
docasné hodnoty vsech sousedu vybraného vrcholu, kterých je méne nez N.
Celkem se tedy vykoná nejvýse pocet operací úmerný N2. Pri pruchodu do
sírky navstívíme a zaradíme do fronty kazdé z N mest nejvýse jednou a
pri jeho vyzvednutí z fronty musíme zpracovat jeho sousedy, kterých je
méne nez N. Celý pruchod do sírky proto vyzaduje provést rádove
nejvýse N2 operací. Vyhledání výsledné cesty zpetným chodem po
predchudcích je pak jiz triviální zálezitostí a vykoná se v lineárním
case. Celkove má nase resení úlohy kvadratickou casovou slozitost.