# ADS úlohy C - Cheating

(Značení: $s$-start, $c$ - cíl, $uv$ - zkratka (obecně), $u,v$ - vrcholy incidentní zkratce , $G$ - graf bez zkratek, $H$ - graf se zkratkami)

Dijkstrův algoritmus se s "normálním" bludištěm dokáže vypořádat v čase $O((n+m) * log\space{n})$.

Pokud tento algoritmus použiji na každý graf, ve kterém se nachází právě jedna zkratka ,a na konci pak vyberu ten graf, který má vzdálenost do cíle nejkratší, výsledný algoritmus bude trvat $O(z * (n+m) * log\space{n})$ .

Druhou extrémní možností je použít Floyd-Warshallův algoritmus , který zvládne vypočítat vzdálenosti mezi všemi vrcholy na grafu bez zkratek. Poté pro každou zkratku $uv$ spočítám: $d(su)+h(uv)+d(vc)$ a porovnám s $d(sc)$; Rozdíl pak vyjadřuje, o kolik je "normální" cesta start-cíl horší než cesta se zkratkou. Samotný algoritmus pro výpočet férových vzdáleností pak má složitost $O(n^3)$.

V obou případech nakonec musím cestu vyhledat. To je jednoduchá úloha pro oba algoritmy - začnu od cíle a hledám nejbližší sousední vrchol s nejkratší vzdáleností od startu, což je (asymptoticky) zanedbatelné (pro orientovaný graf musím jít proti směru hran, proto je tento krok popsán trochu obecněji).

Jak tento způsob lze vylepšit? Musím navíc uvažovat i nad tím, že dolní mez bude $\Omega((n+m) * log\space n)$, jelikož nemůžu spočítat vzdálenost z vrcholu do vrcholu bez výpočtu vzdáleností do ostatních vrcholů (obecně).

Proto volím Floyd-Warshallův algoritmus způsob, jelikož hran může být až $n^2$ (a pro Dijkstrův algoritmus bych se tak dostával na čtvrtou mocninu).

----
(Optimalizace pro velký počet zkratek - bohužel, asymptoticky si moc nepomohu:)

- Mohu zahodit zbytečné zkratky, tzn. ty, které mi cestu prodlužují. Určitě dokážu spočítat vzdálenost $d(su)$ a $d(sv)$ najednou. Ačkoli nevím, jaká je přesně vzdálenost $d(uv)$ bez zkratky, nemá smysl tuto zkratku uvažovat v případě, že $d(su)+h(uv)\geq d(sv)$ (pro $d(su)<d(sv)$).

- Dále mohu využít toho, že shoduje-li se zkratková hrana s normální (a leží-li na minimální cestě), pak nemusím graf přepočítávat celý a $min:=(min-hrana+zkratka)$.

----

Celkový algoritmus
Vstup: Graf $G$ s normálními hranami a zkratkami, ohodnocení hran $h(ab)$
1. Provedu Floyd-Warshall na graf bez zkratek, dostanu matici vzdáleností $D$
2. $minimum = D_{sc}$
3. Pro každou zkratku mezi dvěma vrcholy (označím $u,v$ a délku jako $h(uv)$):
1. Porovnej$(minimum;D_{su}+D_{vc}+h(uv)$
2. je-li druhá hodnota menší, přepiš minimum a pamatuj si zkratku.
3. Je-li zkratka hranou (pokud ne, pak je nejvýhodnější cestou ta férová):
1. Přidej zkratku do grafu G
2. Dokud $start \neq u$:
1. Hledej hranu vycházející z vrcholu $start$, která vede do vrcholu $x$ s nejnižší hodnotou $D_{start,x}$
2. Tento vrchol označ jako $start$
3. Tuto hranu označ jako nejrychlejší
3. Označ hranu $uv$ jako nejrychlejší
4. Označ vrchol $v$ jako $start$
8. Dokud $start \neq cíl$:
1. Opakuj kroky popsané v 4.2., ale teď hledám nejnižší hodnotu $D_{x,cíl}$
9. Výstup: cesta složená z nejrychlejších hran.

Složitost: Výpočet matice je $O(n^3)$, porovnávání je $O(z)$, hledání nejrychlejších hran je $O(n+m)$ (každou hranu mi stačí zvažovat pouze jednou). Jelikož $m,z \leq n^2$, celkově složitost vychází na $O(n^3)$.