a)

Povedzme, že Lukáš začína vo vrchole Linux vpravo dole. Po vyskúšaní rôznych ciest nám môžu vyjsť následovné najmenšie možné náročnosti:

• Z vrcholu Linux do vrcholu Linux je náročnosť $0$
• Z vrcholu Linux do vrcholu Jablko je náročnosť $6$
• Z vrcholu Linux do vrcholu Okná je náročnosť $4$
• Z vrcholu Linux do vrcholu Auto je náročnosť $6$
• Z vrcholu Linux do vrcholu Posilka je náročnosť $14$
• Z vrcholu Linux do vrcholu Pokemon je náročnosť $16$
• Z vrcholu Linux do vrcholu PRASK je náročnosť $13$
• Z vrcholu Linux do vrcholu Peniaze je náročnosť $15$
• Z vrcholu Linux do vrcholu FKS je náročnosť $13$
• Z vrcholu Linux do vrcholu Dievča je náročnosť $17$

Všimnime si, že do troch vrcholov susediacich s Linuxom najmenšiu náročnosť vždy poznáme bez toho aby sme skúšali a porovnávali viaceré možnosti - je to jednoducho náročnosť hrany medzi nimi. Pre ostatné vrcholy však musíme vymyslieť niečo múdrejšie, ak sa nám to nechce len tak skúšať.

b)

Tento postup nefunguje vždy správne. Dá sa totiž chápať dvoma rôznymi spôsobmi a ani jeden z nich nefunguje. Ak si Lukáš nepamätá, ktoré vrcholy už navštívil, môže sa stať, že sa bude stále pohybovať medzi niekoľkými vrcholmi dookola a algoritmus sa nikdy neskončí. Ani keď si navštívené vrcholy pamätá, postup stále nemusí nájsť najkratšiu cestu. To, že je aktuálne jedna hrana najlacnejšia, ešte neznamená, že cesta vedúca cez ňu bude najvýhodnejšia celkovo. Algoritmus robí rozhodnutia iba podľa momentálnej situácie a neberie do úvahy, čo ho čaká ďalej v grafe. Takýto „chamtivý“ (greedy) prístup preto vo všeobecnosti nestačí na hľadanie najkratších ciest v ohodnotených grafoch.

c)

Postup, ktorý použijeme na riešenie takéhoto problému sa nazýva Dijkstrov algoritmus.
Na začiatku si ku každému vrcholu uložíme vzdialenosť od štartu. Štartovací vrchol dostane hodnotu $0$, pretože sa v ňom už nachádzame, a všetky ostatné vrcholy dostanú hodnotu $\infty$, keďže k nim zatiaľ nepoznáme žiadnu cestu.
Potom budeme opakovane vyberať nespracovaný vrchol s najmenšou známou vzdialenosťou. Keď takýto vrchol vyberieme, pozrieme sa na všetkých jeho susedov a skontrolujeme, či sa cez aktuálny vrchol nedá dostať lacnejšie než doteraz. Ak áno, uloženú vzdialenosť prepíšeme na menšiu hodnotu.
Keď vrchol spracujeme, označíme ho ako hotový. Vďaka tomu, že všetky hrany majú nezáporné váhy, vieme, že sme už pre tento vrchol našli najkratšiu možnú cestu a jeho vzdialenosť sa už nikdy nebude meniť.
Tento postup opakujeme dovtedy, kým nespracujeme všetky vrcholy alebo kým už neexistuje ďalší dosiahnuteľný nespracovaný vrchol.
Po skončení algoritmu budeme mať pri každom vrchole uloženú najmenšiu možnú náročnosť cesty zo štartu.

Takto má Dijkstrov algoritmus časovú náročnosť $O(V^2+E)$, ($E$ je počet hrán a $V$ je počet vrcholov). To po prídape vieme zlepšiť tým, že použijeme prioritnú frontu, v ktorej si budeme pamätať vzdialenosti do nespracovaných vrcholov namisto obyčajného poľa. Tak zrýchlime vyhľadávanie nespracovaného vrcholu s najmenšou vzdialenosťou. Takýto Dijkstra má potom časovú náročnosť $O((V^2+E)\log V)$.

d)

Tento prístup môže fungovať, ale môže byť veľmi neefektívny.
BFS funguje dobre pri neohodnotených grafoch, pretože všetky hrany majú rovnakú cenu. Pri rôznych váhach sa však môže stať, že neskôr objavíme oveľa lepšiu cestu do vrcholu, ktorý sme už dávno spracovali. Potom musíme znova aktualizovať všetky vrcholy, ku ktorým z neho vedú cesty.
Toto sa môže opakovať veľakrát. Algoritmus teda môže stále dokola prepisovať vzdialenosti a opakovane prechádzať tie isté časti grafu. Pri väčších grafoch sa tým výrazne spomalí.
Dijkstrov algoritmus sa tomuto problému vyhýba tým, že vrcholy spracúva v poradí podľa aktuálnej najmenšej vzdialenosti. Keď raz spracuje nejaký vrchol, vie, že jeho vzdialenosť už je definitívne správna a nebude ju musieť neskôr meniť.

V najhoršom prípade môže takéto prepisovanie viesť až k časovej náročnosti $O(VE + V + E)$, pretože jeden vrchol aj jeho susedia sa môžu opakovane vracať do prepisovať. Tu vidíme, že ak pri grafoch, kde $E > V$ (ako napríklad aj náš graf Lukášových rozhodnutí), je toto podstatne horšia časová náročnosť ako Dijkstrov $O(V^2+E)$.