# Ads úlohy C - Zakázka

Správná funkce $\pi$ umožňuje rekonstruovat nejkratší cesty bez znalosti jejich délky. Chci-li se tak dostat na vrchol $a$, musím projít vrcholy $s, \dots, \pi(\pi(a)), \pi(a)$.

Označím $u=\pi(v)$. Ze třetí a čtvrté podmínky dostávám následující:

$d(v)\leq d(u)+w(u,v)$
$d(v)=d(u)+w(u,v)$

$d(u)=d(v)-w(u,v)$
$w(u,v)\geq d(v)-d(u)$

Tyto podmínky by měly zajistit, že směrem k výchozímu vrcholu se vzdálenost snižuje.

Problém nastane ve chvíli, kdy $w(u,v)$ je nula, protože v takovém případě $\pi(v)$ může být jakýkoli soused, ne pouze ležící na nejkratší cestě (ve skutečnosti bude vzdálenost stejná, ale s větším počtem hran). Zároveň tak musí být $\pi(u)=v$, jelikož vrchol $u$ je dosažitelný.

Vezmu-li si tak jakýkoli graf s vyhovujícími podmínkami, k libovolnému dosažitelnému vrcholu $v$ (kromě startu) přidám souseda $u$ tak, že $w(v,u)=0$, $w(v,u)=0$, $\pi(u)=v$ a $\pi(v)=u$, dostávám neplatné řešení.

Toto se dá zobecnit i na jakékoli nulové cykly (v orientovaném grafu je obyčejná hrana cyklus délky 2) - tzn. pro graf, který bude obsahovat nulový cyklus začínající a končící ve $v$, může existovat špatné řešení.

Vše je založeno na tom, že algoritmy pro hledání cest nenajdou nejkratší cestu, ale nejkratší sled - proto nefungují pro záporné cykly (a hledání cest v takových případech je nadpolynomiálně těžké). Stejně tak se v těchto algoritmech předchůdce mění jen v případě, že se $d(v)$ sníží.

Podmínka, která správnost funkce $\pi$ zajistí, je naznačena v prvním odstavci a může znít např. následovně: *Graf tvořený vrcholy výchozího grafu $G$ a hranami $\pi(v),v$ ($v \in G$) je kostrou grafu $G$.* (Tím nejkratší cesta do každého dosažitelného vrcholu existuje z výchozího vrcholu a je určena jednoznačně.)