Váhy vrcholů
Úloha číslo: 4141
Mějme vrcholově ohodnocený graf, tedy graf \(G=(V,E)\) a váhovou funkci \(w:V\to \mathbb R^+\). Váha cesty je dána součtem vah vrcholů, jimiž cesta prochází. Upravte Dijkstrův algoritmus tak, aby nalezl cestu nejmenší váhy mezi dvěma danými vrcholy.
Řešení
V Dijkstrově algoritmu postačí změnit aktualizace odhadu vzdálenosti \(d\) z
\(\forall y\in N(x): d(y)=\min\{d(y),d(x)+l(x,y)\}\)
na
\(\forall y\in N(x): d(y)=\min\{d(y),d(x)+w(y)\}\).
Podobně jako v Dijkstrově algoritmu odhad upravíme, pokud se do \(y\) dá dostat lépe přes \(x\).