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)\le d(u)+w(u,v)$

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

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

$w(u,v)\ge 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ě.)