Bottleneck problém

Úloha číslo: 4142

Modifikujte Dijkstrův algoritmus, aby vyřešil tzv. bottleneck problem: V orientovaném váženém grafu je třeba určit cestu tak, aby váha její nejtěžší hrany byla co nejmenší.

  • Řešení

    Nyní \(d(y)\) bude odhad na váhu nejtěžší hrany na nějaké cestě z \(u\) do \(y\).

    \(\forall y\in N(x): d(y)=\min\{d(y),\max\{d(x),l(x,y)\}\}\)

    Podobně jako v Dijkstrově algoritmu odhad upravíme, pokud se do \(y\) dá dostat lépe přes \(x\).

    Třeba si uvědomit, že váha cesty vedoucí do \(y\) přes \(x\) je rovna většímu z čísel: (již definitivní) váhy cesty do \(x\) a váhy hrany \((x,y)\).

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