1 votos

Encuentra un camino desde $s$ hasta $t$ con el "cuello de botella" más pequeño

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.

1voto

raiym Puntos 103

De hecho, puedes usar una variante del Algoritmo de Prim con las siguientes modificaciones:

  1. Para cada nodo $v$ almacenamos el peso de un camino con peso máximo mínimo $d[v]$. Inicialmente todos estos pesos están establecidos en $d[v] = \infty$ excepto por $d[s] = 0$.

  2. Supongamos ahora que el nodo con el costo mínimo es $u$. Para cada vecino $v_i$ de $u$ debemos actualizar el costo $c[v_i]$ y establecer el peso máximo $d[v_i]$ del camino hasta ahora.

  3. Para establecer el costo $máximo$ $c[v_i]$ primero verificamos si $\max\{d[u], w(u,v_i)\} < d[v_i]$, y si es verdad, actualizamos $d[v_i] = \max\{d[u], w(u,v_i)\}$.

Similar a tu otra pregunta, el algoritmo puede ser implementado en tiempo lineal usando una cola de cubos.

Nota que una sola operación de extracción mínima podría tomar $\mathcal{O}(\lvert V \rvert)$ aquí, en contraste a tu otra pregunta. Sin embargo, puedes mantener un apuntador al cubo correspondiente al peso mínimo retornado en la última operación. Luego o bien retornas el siguiente elemento del mismo cubo (si aún no está vacío) o avanzas el apuntador hasta llegar a un cubo no vacío. Al final, el apuntador habrá recorrido una vez todos los cubos. Por lo tanto, el costo amortizado para todas las operaciones de extracción mínima es $\mathcal{O}(\lvert V \rvert)$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X