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

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email