Lukáš sa rozhodol, že prestane používať Linux a nájde si dievča. Keďže je to však informatik, reprezentoval si cestu k dievčaťu grafom. Pomôž Lukášovi nájsť najkratšiu trasu od jeho aktuálneho stavu k jeho vysnívanému dievčaťu.

Úloha

Lukášov postup vieme zakresliť ako ohodnotený graf. Vrcholy reprezentujú jednotlivé stavy, v ktorých sa môže nachádzať, a hrany predstavujú možné prechody medzi nimi. Každá hrana má priradenú hodnotu, ktorá vyjadruje „náročnosť“ daného kroku (napríklad čas alebo úsilie). Lukáš začína v jednom z vrcholov a zaujíma ho, ako sa čo najefektívnejšie dostať k jednotlivým vrcholom.

a. Pre každý vrchol urč najmenšiu možnú „náročnosť“, za ktorú sa doň Lukáš vie dostať zo štartovacieho vrcholu.

b. Lukáš si vymyslel nasledovný postup:
„Zo svojho aktuálneho vrcholu sa vždy presuniem do susedného vrcholu, do ktorého vedie najmenej náročný prechod. Tento krok budem opakovať.“

Funguje tento postup vždy správne?
Ak nie, vysvetli prečo a uveď konkrétny príklad grafu, na ktorom tento postup zlyhá.

c. Navrhnite všeobecný postup, ktorý pre ľubovoľný ohodnotený graf s nezápornými hranami určí najmenšiu náročnosť cesty zo štartovacieho vrcholu do všetkých ostatných vrcholov.
Tvoj postup popíš dostatočne presne, aby sa dal jednoznačne vykonať.
d. Lukáš má teraz veľa práce, musí chodiť do posilky, riešiť FKS a loviť Julku pokeballmi, takže sa mu nechcelo kódiť hľadanie najkratšej cesty. Tak rozmýšlaľ a potom si uvedomil, že by mohol zrecyklovať kód z BFS, len by si pre každý vrchol pamätal vzdialenosť a vždy keď nájde kratšiu cestu ako má, prepíše ju.
Prečo by bolo takéto riešenie neefektívne prípadne by vôbec nefungovalo? Popíš (alebo nakresli) graf, na ktorom to ukážeš.