Keďže Lukáš nezvládal telefonovanie, niektoré ženy sa cítili smutné a zanedbané. Týmto prístupom sa mu podarilo mať negatívne vzťahy s viacerými z nich. Lukáš si preto svoj život predstavil ako orientovaný graf – vrcholy sú ľudia a hrany medzi nimi hovoria, ako sa vie dostať z jedného vzťahu do druhého.

Niektoré vzťahy ho stoja energiu, čas alebo peniaze, takže majú kladnú cenu. Iné mu naopak pomôžu a „zlepšia situáciu“, takže môžu mať aj zápornú cenu. Lukáš sa teraz snaží nájsť najlacnejšie cesty v grafoch, kde sa môžu nachádzať aj záporné hrany.

a)

Lukáš sa rozhodol použiť Dijkstrov algoritmus, pretože fungoval dobre na obyčajných grafoch. Lenže teraz sa v grafe nachádzajú aj záporné hrany.

Nakresli príklad grafu, na ktorom Dijkstrov algoritmus nefunguje správne a stručne vysvetli prečo. Popíš ako algoritmus postupuje, ktoré vzdialenosti si zapamätá a kde spraví chybu. Vysvetli aj to, prečo je problém práve v záporných hranách. (Ak nevieš, čo je to Dijkstrov algoritmus, neboj sa nájsť na Google nejaké vysvetlenie)

b)

Lukáš si povedal:

„Tak ja použijem BFS, ale budem si pamätať najlepšiu známu vzdialenosť do každého vrcholu. A keď nájdem lepšiu, tak ju prepíšem.“

Teda graf prechádza podobne ako pri BFS, ale vzdialenosti môže meniť aj viackrát.

Funguje tento postup vždy správne aj v grafoch so zápornými hranami? Ukáž prečo áno alebo nie. Ak nefunguje, nájdi graf, na ktorom zlyhá, a vysvetli čo sa pokazí.

c)

Lukáš si po chvíli všimol, že jeho nový postup sa nie vždy zastaví.

Nájdi a nakresli graf so záporným cyklom, na ktorom bude Lukáš stále nachádzať lepšie a lepšie cesty. Jeho vzdialenosti sa budú stále zmenšovať a algoritmus nikdy neskončí.

Vysvetli čo je záporný cyklus a prečo kvôli nemu vlastne neexistuje najkratšia cesta.

d)

Lukáš skúša ďalší postup.

Najprv raz prejde všetky hrany a vždy keď nájde lepšiu cestu do nejakého vrcholu, zlepší si vzdialenosť. Potom prejde všetky hrany znova. Potom ešte raz. A tak ďalej.

Keďže v grafe môžu byť záporné hrany, môže sa stať, že lepšiu cestu objaví až po viacerých prechodoch.

Vysvetli čo sa deje po každom prechode cez všetky hrany. Čo vieme povedať o cestách, ktoré Lukáš pozná po prvom, druhom alebo treťom prechode? Ako to súvisí s počtom hrán na ceste?

Ak má graf N vrcholov, koľkokrát stačí prejsť všetky hrany, aby Lukáš určite našiel najkratšie cesty, ak v grafe neexistuje záporný cyklus?

e)

Lukáš skúša ešte niečo iné.

Pre každý pár vrcholov A, B sa pýta:

„Neviem ísť z A do B lacnejšie, ak medzi tým prejdem cez nejaký ďalší vrchol K?“

Najprv dovolí len priame cesty. Potom dovolí cesty cez jeden ľubovoľný vrchol. Potom cez dva vrcholy. Potom cez ďalšie a ďalšie.

Keďže v grafe môžu byť záporné hrany, nové medzivrcholy môžu odhaliť výrazne lacnejšie cesty, ktoré predtým nebolo vidno.

Opíš, čo sa zmení, keď Lukáš prvýkrát dovolí medzivrcholy. Vysvetli, prečo sa po povoľovaní ďalších vrcholov objavujú nové lacnejšie cesty a prečo sa týmto postupom nakoniec dostane ku všetkým najkratším cestám medzi všetkými dvojicami vrcholov, ak v grafe neexistuje záporný cyklus.