Bottleneck problem
Task number: 4166
Modify Dijkstra’s algorithm to solve the so-called bottleneck problem: In an oriented weighted graph, it is necessary to determine the path so that the weight of its heaviest edge is as small as possible.
Solution
Now \( d(y) \) will estimate the weight of the heaviest edge on any path from \( u \) to \( y \).
\(\forall y\in N(x): d(y)=\min\{d(y),\max\{d(x),l(x,y)\}\}\)
As in Dijkstra’s algorithm, we adjust the estimate if \( y \) can be better accessed via \( x \).
It should be noted that the weight of the path leading to \( y \) via \( x \) is equal to the greater of the numbers: the (already definitive) weight of the path to \( x \) and the weight of the edge \( (x, y) \).
