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