Záporné hrany
Úloha číslo: 4139
Sestrojte příklad grafu s jednou záporně ohodnocenou hranou, na němž Dijkstrův algoritmus selže.
Ve které části důkazu správnosti Dijkstrova algoritmu byl potřeba předpoklad nezápornosti délek hran?
Řešení
Pokud dovolíme záporné délky hran, nemusí platit trojúhelníková nerovnost.
Vezměme si např. \(G=C_3\) s délkami \(l(u,v)=1\), \(l(u,w)=2\), \(l(v,w)=-2\).
Dikstrův algoritmus přednostně zpracuje \(v\) a oznámí, že \(dist(u,v)=1\), zatímco by cesta přes \(w\) měla celkovou délku \(0\).
