Find a path from $s$ to $t$ with smallest "bottleneck" 
Let an undirected graph, $G=(V,E)$ with weights defined by the function $w:E\to\mathbb{N}$ and for each edge: $1\le w(e) \le |V|$. You are given two vertices: $s,t\in V$. Find a path from $s$ to $t$ where the maximum weight is minimal. 

Basically I thought about utilizing DFS with a small modification:
We scan the graph from $s$ using DFS only we may add a vertex to the queue more than one time. We keep for each vertex a value $light[v]$. Now, consider a gray vertex, $v$ (meaning, a vertex which already scanned). Suppose there's an edge $\langle u,v\rangle$ such that $$w(u,v) < light[v]$$ then we update $light[v] = w(u,v)$ and insert $v$ to the queue once again.
I want to verify the correctness of my suggested algorithm. Also, is this linear? ($O(|V| +|E|$). I am not sure about that since basically each vertex could be added to the queue several times.
 A: Actually, you can use a variant of Prim's Algorithm with the following modifications:


*

*For each node $v$ you store the weight of a path with minimal maximum weight $d[v]$. Initially all these weights are set to $d[v] = \infty$ except for $d[s] = 0$.

*Let's say now that the node with the minimum cost is $u$. For each neighbor $v_i$ of $u$ we should update the cost $c[v_i]$ and set the maximum weight $d[v_i]$ of the path so far.

*To set the $maximum$ cost $c[v_i]$ first we check if $\max\{d[u], w(u,v_i)\} < d[v_i]$, and if true, update $d[v_i] = \max\{d[u], w(u,v_i)\}$.
Similar to your other question, the algorithm can be implemented in linear time using a bucket queue.
Note that a single extract min operation might take $\mathcal{O}(\lvert V \rvert)$ here, in contrast to your other question. However, you can keep a pointer to the bucket corresponding to the minimum weight returned in the last operation. Then you either return the next element from the same bucket (if it is not yet empty) or you advance the pointer until you reach a non-empty bucket. In the end, the pointer will have iterated once over all buckets. Thus, the amortized cost for all extract min operations is $\mathcal{O}(\lvert V \rvert)$.
