1. Problematické vzťahy
Zadanie
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
AdoBlacnejšie, ak medzi tým prejdem cez nejaký ďalší vrcholK?“
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.
by Tomáš
a) Prečo Dijkstra nefunguje so zápornými hranami
Na začiatok, čo je to vlastne Dijkstra?
Dijkstrov algoritmus hľadá najkratšie cesty zo štartu do všetkých ostatných vrcholov v grafe. Udržiava si vzdialenosti ku každému vrcholu a postupne vždy vyberie ten vrchol, ktorý má momentálne najmenšiu známu vzdialenosť. Tento vrchol označí ako „hotový“ a už ho nikdy neskôr neupravuje. Následne sa pokúsi zlepšiť vzdialenosti jeho susedov cez tento vrchol.
Dijkstra predpokladá, že keď vyberie vrchol s najmenšou aktuálnou vzdialenosťou, táto vzdialenosť je už definitívna. Toto platí iba v grafoch s kladnými hranami, kde každá ďalšia hrana môže vzdialenosť iba zväčšiť.
Ak však existuje záporná hrana, môže sa stať, že vrchol, ktorý už bol označený ako „hotový“, by sa neskôr dal zlepšiť cez inú cestu. Dijkstra už jeho susedov neprepočítava, takže lepšiu cestu nenájde. Preto algoritmus zlyhá v grafoch so zápornými hranami.
Ak sa chceš o Dijkstrovom algoritme naučiť viac, pozri KSP kuchárku:
https://ksp.sk/kucharka/dijkstra/
Príklad
Chceme sa dostať z vrcholu S do vrcholu CIEL v čo najkratšom čase. Dijkstra používa prioritnú frontu, a tak tento graf by algoritmus prešiel takto:
- (A,1) alebo (B,2) → vyberie A
- (D,3),(B,2) → vyberie B
- (D,3),(C,7) → vyberie D
- (CIEL,5),(C,7) → vyberie CIEL a skončí
To, že graf má zápornú hranu, ani nezistil. Lepšia cesta je pritom S → B → C → E → CIEL za cenu 2.
b) Prečo BFS‑štýlový algoritmus nefunguje na vážených grafoch
BFS funguje iba v nevážených grafoch, kde každá hrana má rovnakú cenu. V takom prípade najkratšia cesta znamená „najmenej hrán“.
V našej úlohe však hrany majú rôzne váhy. Algoritmus, ktorý spracuje vrchol len raz (ako BFS), ale má váhy a môže ich meniť, sa stále správa ako BFS. Preto môže skončiť hneď, keď prvýkrát dorazí do cieľa, hoci existuje lacnejšia cesta, ktorá má viac hrán.
Príklad
BFS pôjde:
- (A,1), (B,2)
- (D,3), (C,7)
- (CIEL,5), (E,14)
A skončí, lebo BFS predpokladá, že prvá nájdená cesta má najmenej hrán.
V hodnotenom grafe to ale neznamená, že je najlacnejšia.
c) Prečo v grafe so záporným cyklom neexistuje najkratšia cesta
Záporný cyklus je cyklus, ktorého celková cena je záporná. Ak sa do takého cyklu dá vstúpiť, môžeme ho obchádzať stále dokola a zakaždým znížiť celkovú cenu cesty.
To znamená, že neexistuje žiadna „najkratšia“ cesta — vždy existuje ešte kratšia, ak cyklus prejdeme o jedenkrát viac.
Príklad
A → B → C → A, kde hrany majú ceny 1, −3 a 1.
Cena cyklu je −1.
Dvakrát → −2
Trikrát → −3
… nikdy sa to nezastaví.
d) Prečo Bellman–Ford potrebuje práve (V−1) prechodov
Bellman–Ford hľadá najkratšie cesty aj v grafoch so zápornými hranami. Na rozdiel od Dijkstru sa nespolieha na „definitívne“ vzdialenosti.
Robí jednu vec dokola: relaxuje hrany.
Čo je relaxácia?
Relaxácia znamená:
Skúsim, či sa do v nedá dostať lacnejšie cez u.
Ak áno, prepíšem dist[v].
Relaxácia = zlepšenie ceny.
Prečo (V−1) prechodov?
Najdlhšia najkratšia cesta bez cyklov má najviac V−1 hrán.
Preto:
-
- prechod → cesty s 1 hranou
-
- prechod → cesty s 2 hranami
- …
- (V−1). prechod → cesty s (V−1) hranami
Po (V−1) prechodoch už musíme mať všetky najkratšie cesty.
Čo ak sa ešte niečo zlepší?
Existuje záporný cyklus.
e) Ako funguje Floyd–Warshall
Floyd–Warshall hľadá najkratšie cesty medzi všetkými dvojicami vrcholov naraz.
Používa tabuľku dist[A][B], ktorá obsahuje najlepšiu známu cenu cesty.
Postup
- Najprv pozná iba priame hrany.
- Potom dovolí jeden medzivrchol K.
- Skúma, či A → K → B je lacnejšie než A → B.
- Toto zopakuje pre každý vrchol K.
Výsledok
Po spracovaní všetkých vrcholov tabuľka obsahuje najkratšie možné cesty medzi všetkými dvojicami.
