Camino más corto en un grafo con aristas y vértices ponderados

Question

Me planteo un problema de planificación de rutas (a partir de una fuente $s$ para hundir $t$ ) en un grafo no dirigido con aristas y vértices ponderados. El objetivo es encontrar el camino más corto entre el origen $s$ y el fregadero $t$ . Intuitivamente, la longitud del camino es la suma de los pesos de las aristas y los vértices de los caminos (formalmente, sea $k$ sea el número de aristas de un camino: $\sum_{i=0}^k c(v_i) + \sum_{i=1}^k w(v_i1, v_i)$ ).

Una primera idea que se me ocurrió, fue sustituir cada vértice por una camarilla de $\delta(v)$ vértices (es decir, igual a su grado).

Cada arista incidente en el vértice se asignará a uno solo de los vértices de la camarilla.

Cada arista de la camarilla $C_{v_i}$ será igual al coste $c(v_i)$ . De esta forma se obliga al algoritmo a cambiar a la fuerza en una arista de la camarilla (simulando el pago del coste del vértice al que se ha sustituido).

Dejemos que $G'$ el gráfico resultante de esta transformación, ejecuta sobre él el algoritmo de Dijkstra para encontrar el camino más corto desde $s$ a $t$ .

Desgraciadamente no he podido demostrar que es correcto el coste de construcción de $G'$ (para ser sincero, ni siquiera estoy seguro de que esto sea una buena idea).

¿Puede alguno de ustedes ayudarme?

Answer 1

En lugar de sustituir un nodo $v$ por una camarilla, sustituirla por una arista $(v_1,v_2)$ con peso $c(v)$ y enlazar todos los vecinos de $v$ a $v_1$ y $v_2$ .

Answer 2

Para simplificar, supondré que su gráfico es sencillo. Dejemos que $w': E \rightarrow \mathbb{R}$ sean nuevos pesos de aristas definidos como: $$w'([u,v]) = w([u,v]) + \frac{c(u)}{2} + \frac{c(v)}{2}$$ Dejemos que $\gamma = v_0 \rightarrow v_1 \rightarrow \cdots \rightarrow v_n$ un camino en el gráfico. La longitud del camino tal y como lo has definido es: $$\begin{align*} l(\gamma) &= \sum_{k = 0}^{n} c(v_k) + \sum_{k=0}^{n-1} w([v_k,v_{k+1}]) \\ &= \sum_{k=0}^{n} \frac{1}{2}c(v_k) + \sum_{k=0}^{n} \frac{1}{2}c(v_k) + \sum_{k=0}^{n-1} w([v_k,v_{k+1}]) \\ &= \left( \frac{1}{2}c(v_n)+\sum_{k=0}^{n-1} \frac{1}{2}c(v_k) \right) + \left(\frac{1}{2}c(v_0)+ \sum_{k=0}^{n-1} \frac{1}{2}c(v_{k+1})\right) + \sum_{k=0}^{n-1} w([v_k,v_{k+1}]) \\ &= \frac{1}{2} c(v_0) + \frac{1}{2} c(v_n) + \sum_{k=0}^{n-1} \left( w([v_k,v_{k+1}]) + \frac{1}{2}c(v_{k})+ \frac{1}{2}c(v_{k+1}) \right) \\ &= \frac{1}{2} c(v_0) + \frac{1}{2} c(v_n) + \sum_{k=0}^{n-1} w'([v_k,v_{k+1} ]) \end{align*}$$ Por lo tanto, es la longitud del camino con sólo los pesos de las aristas $w'$ además de los términos de los límites que no importarán ya que estás fijando los puntos finales de todos modos.