Consideremos un grafo no dirigido, $G=(V,E)$, con pesos definidos por la función $w:E\to\mathbb{N}$ y para cada arista: $1\le w(e) \le |V|$. Se te dan dos vértices: $s,t\in V$. Encuentra un camino de $s$ a $t$ donde el peso máximo sea mínimo.
Básicamente pensé en utilizar DFS con una pequeña modificación:
Recorremos el grafo desde $s$ utilizando DFS, pero podemos agregar un vértice a la cola más de una vez. Mantenemos para cada vértice un valor $light[v]$. Ahora, considera un vértice gris, $v$ (es decir, un vértice que ya ha sido recorrido). Supongamos que hay una arista $\langle u, v\rangle$ tal que $$w(u,v) < light[v]$$ entonces actualizamos $light[v] = w(u,v)$ e insertamos $v$ en la cola una vez más.
Quiero verificar la corrección de mi algoritmo sugerido. Además, ¿es lineal esto? ($O(|V| + |E|$). No estoy seguro de eso, ya que básicamente cada vértice podría ser agregado a la cola varias veces.