El problema de camino mínimo

Dado un grafo dirigido $G = (V, E)$ y una función de peso $w : E \to \R$ definimos:

• El peso $w(p)$ de un camino $p = \langle v_0, …, v_k\rangle$ como la suma de sus aristas. Es decir

  $$ w(p) = \sum_{i=1}^k w(v_{i-1}, v_i) $$

• El peso del camino mínimo de $u$ a $v$ como

  $$ \delta(u,v) = \begin{cases} \min\{w(p) : u \stackrel{p}{\leadsto} v\} \qquad&\text{si hay camino de $u$ a $v$} \\ \infty \qquad&\text{caso contrario} \end{cases} $$

• Un camino mínimo de $u$ a $v$ es cualquier camino $p$ de peso $\delta(u, v)$.

Variantes

Nos centramos en el problema de camino míninimo de un vértice source a todos los vértices $v \in V$ (single-source shortest-paths), principalmente porque los algoritmos que veremos para resolverlo son también útiles para resolver las siguientes variantes

1. Camino mínimo de todo nodo a un único destino (single-destination shortest-paths). Invirtiendo las direcciones de las aristas convertimos este problema en un problema de single-source.
2. Camino mínimo de $u$ a $v$ para algún par $u,v \in V$ (single-pair shortest-path). Al resolver el problema single-source también resolvemos este problema en particular. Más aún, todos los algoritmos que conocemos para resolver la versión single-pair tienen asintóticamente la misma complejidad en el peor caso que los algoritmos que veremos a continuación para single-source.
3. Camino mínimo de $u$ a $v$ para todo par de nodos $u,v \in V$ (all-pairs shortest-paths). Si bien podemos resolver este problema utilizando algoritmos que resuelven la versión single-source, existen algoritmos más óptimos para este problema particular. Los veremos en el capítulo 25.

Subestructura óptima

La gran mayoría de los algortimos que resuelven el problema de camino mínimo en alguna de sus versiones se basan en la propiedad de que los subcaminos de un camino mínimo son a su vez caminos mínimos.

Teorema

Dado un grafo $G = (V, E)$ dirigido con una función de peso $w : E \to \R$, sea $p = \langle v_0, …, v_k \rangle$ un camino mínimo de $v_0$ a $v_k$ y, para cada $i, j \in \N$ tal que $0 \leq i \leq j \leq k$, sea $p_{ij} = \langle v_i, …, v_j\rangle$ el subcamino de $p$ que empieza en $v_i$ y termina en $v_j$. Entonces, $p_{ij}$ es el camino mínimo de $v_i$ a $v_j$.

• Demostración

Ciclos negativos

Si el grafo de entrada contiene ciclos negativos alcanzables desde el vértice source $s$, el camino mínimo no está definido.