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\).

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze