MOR - Tema 3

Camino de menor valor

Conjunto de caminos desde un nodo. Definición

Sea $R = (V, A, p)$ red orientada con raíz de salida $i$, sea $j \in V$ nodo cualquiera denotamos al conjunto de caminos que van de $i$ a $j$ como $\Pi_{ij}$, es decir,

$$\begin{align*} \Pi_{ij} = \{P \mid P \text{ es un camino en } R \text{ que va de } i \text{ a } j\}\\ \end{align*}$$

Valor de un camino. Definición

Sea $R = (V, A, p)$ red orientada con raíz de salida $i$ y sea $\pi_{ij} \in \Pi_{ij}$ camino definido como:

$$\begin{align*} i \xrightarrow[]{p_{i, i_1}} i_1 \xrightarrow[]{p_{i_1, i_2}} i_2 \xrightarrow[]{} \ldots \xrightarrow[]{} i_{m-1} \xrightarrow[]{p_{i_{m-1}, j}} j \end{align*}$$

definimos el valor del camino como la suma de los pesos de los arcos que lo forman:

$$\begin{align*} p(\pi_{ij}) = \displaystyle \sum_{e \in \pi_{ij}} p(e) = p_{i, i_1} + p_{i_1, i_2} + \ldots + p_{i_{m-1}, j}\\ \end{align*}$$

Camino de valor mínimo. Definición

Sea $R = (V, A, p)$ red orientada con raíz de salida $i$ y sea $j \in V$ nodo cualquiera. Definimos el camino de valor mínimo como el camino $\pi_{ij}' \in \Pi_{ij}$ que cumple:

$$\begin{align*} p(\pi_{ij}') = \min_{\pi_{ij} \in \Pi_{ij}} p(\pi_{ij}) \end{align*}$$

Teorema 3.1. Caracterización de los caminos de valor mínimo

Sea $R = (V, A, p)$ red con raíz de salida $i$, se cumple que:

$$\begin{align*} \exists \pi_{ij}' \in \Pi_{ij} \texttt{ CVM } \forall j \in V \iff \nexists \text{ circuitos de valor negativo en } R\\ \end{align*}$$

Valor del camino trivial

Sea $R = (V, A, p)$ red orientada con raíz de salida $i$. Consideramos el camino trivial $\pi_{ii}$ que va desde $i$ a $i$ sin pasar por ningún otro vértice. El valor del camino trivial es:

$$\begin{align*} p(\pi_{ii}) = 0 \end{align*}$$

Consecuencia del Teorema 3.1

A partir del Teorema 3.1, se deduce que si no existen circuitos de valor negativo en la red $R = (V, A, p)$, es suficiente buscar caminos elementales para encontrar los caminos de valor mínimo desde la raíz de salida $i$ al resto de vértices $j \in V$.

Teorema 3.2. Subcaminos de caminos de valor mínimo

Sea $R = (V, A, p)$ red orientada y $\pi_{rs}$ camino de menor valor de $r$ a $s$ en $R$, entonces se tiene que cualquier subcamino $\pi_{ri}$ de $\pi_{rs}$ es un camino de menor valor de $r$ a $i$ en $R$, para cualquier $i$ vértice en $\pi_{rs}$ con $i \neq r$ y $i \neq s$.

Consecuencia del Teorema 3.2

A partir del Teorema 3.2, se deduce que al obtener un camino de valor mínimo desde la raíz de salida $r$ a un vértice $s$, con el mínimo esfuerzo ya tenemos los caminos de valor mínimo desde $r$ a todos los vértices intermedios que forman el camino de $r$ a $s$.

Algoritmo de Ford-Moore-Bellman

Este algoritmo se puede emplear para obtener un camino de valor mínimo desde un vértice fijado a todos los demás vértices de una red orientada independientemente del valor de los pesos de los arcos, es decir, $p(e) \in \mathbb{R}$ para cualquier $e \in A$. No obstante, su tiempo de ejecución es $O(n^2m)$.

Teorema 3.3. Condición suficiente y necesaria para caminos de valor mínimo

Sea $R = (V, A, p)$ red orientada y $d(i)$ el valor de un camino $\pi_{ri}$ desde $r$ a $i$ en $R$, para cada $i \in V$. Entonces, los caminos $\pi_{ri}$ son caminos de valor mínimo desde $r$ a $i$ en $R$ si y solo si se cumplen las siguientes condiciones:

• $d(r) = 0$
• $d(j) \leq d(i) + p_{ij} \quad \forall (i, j) \in A$

Descripción del Algoritmo de Ford-Moore-Bellman

Sea $R = (V, A, p)$ red con raíz de salida $r$, consideramos $p_{ij} \in \mathbb{R}$ para cualquier $(i, j) \in A$ y consideramos que no existen circuitos de valor negativo en $R$ entonces, el algoritmo de Ford-Moore-Bellman se describe a continuación:

1. Tomar $V' = V \setminus \{r\}$ y se definen:

$$\begin{align*} d(i) = \left\{ \begin{array}{ll} 0 & \text{ si } i = r\\ p_{ri} & \text{ si } i \in \Gamma^+(r)\\ +\infty & \text{ en otro caso} \end{array} \right. \qquad \text{y} \qquad I(i) = \left\{ \begin{array}{ll} r & \text{ si } i \in \Gamma^+(r)\\ 0 & \text{ en otro caso} \end{array} \right. \end{align*}$$

2. Sea $v \in V'$ tal que $d(v) = \min_{i \in V'} d(i)$ entonces:

3. Repetir el paso 2 hasta que $V' = \emptyset$

Algoritmo de Dijkstra

El algoritmo de Dijkstra se puede emplear para obtener un camino de valor mínimo desde un vértice fijado a todos los demás vértices de una red orientada siempre que los pesos de los arcos sean no negativos, es decir, $p(e) \geq 0$ para cualquier $e \in A$. Su tiempo de ejecución es $O(n^2)$.

Teorema 3.4. Condición suficiente para caminos de valor mínimo

Sea $R = (V, A, p)$ red orientada con raíz de salida $r$ y $p(e) \geq 0$ para cualquier $e \in A$, una colección de caminos de $r$ a $i$ para cada $i \in V \setminus \{r\}$, cada uno de valor $d(i)$ y, además, existe un conjunto $V' \subseteq V \setminus \{r\}$ tal que:

$$\begin{align*} d(i) = \left\{ \begin{array}{ll} \text{ valor de un CMV de } r \text{ a } i & \text{ si } i \in V \setminus V'\\[2ex] \displaystyle \min_{j \in \Gamma^-(i) \cap (V \setminus V')} \{d(j) + p_{ji}\} & \text{ si } i \in V' \cap \left( \displaystyle \bigcup_{j \in V\setminus V'} \Gamma^+(j)\right) \end{array} \right. \end{align*}$$

Si $v \in V'$ cumple que $d(v) = \displaystyle \min_{i \in V'} d(i)$, entonces $d(v)$ es el valor de un CMV desde $r$ a $v$.

Descripción del Algoritmo de Dijkstra

Sea $R = (V, A, p)$ red con raíz de salida $r$ y $p(e) \geq 0$ para cualquier $e \in A$, entonces el algoritmo de Dijkstra se describe a continuación:

1. Tomar $V' = V \setminus \{r\}$ y se definen:

$$\begin{align*} d(i) = \left\{ \begin{array}{ll} 0 & \text{ si } i = r\\ p_{ri} & \text{ si } i \in \Gamma^+(r)\\ +\infty & \text{ en otro caso} \end{array} \right. \qquad \text{y} \qquad I(i) = \left\{ \begin{array}{ll} r & \text{ si } i \in \Gamma^+(r)\\ 0 & \text{ en otro caso} \end{array} \right. \end{align*}$$

2. Sea $v \in V'$ tal que $d(v) = \min_{j \in V'} d(i)$ entonces:

3. Repetir el paso 2 hasta que $V' = \emptyset$

Transformaciones monótonas de redes orientadas

En general, los caminos de valor mínimo en una red orientada no se mantienen bajo transformaciones estrictamente crecientes de los pesos de los arcos.

Transformación $kx$

No obstante, existe una transformación monótona que si permite relacionar los caminos de valor mínimo. Se define como:

$$\begin{align*} f(x) = k \cdot x \end{align*}$$

Así, consideramos la transformación de una red orientada $R = (V, A, p)$ en otra red orientada $R' = (V, A, p')$ y, por tanto, $p'(e) = k \cdot p(e)$ para cualquier $e \in A$ y $k \in \mathbb{R} \setminus \{0\}$.

De esta forma, sea $\pi$ un camino cualquiera en $R$, entonces:

$$\begin{align*} p'(\pi) = \displaystyle \sum_{e \in \pi} p'(e) = \displaystyle \sum_{e \in \pi} k \cdot p(e) = k \cdot \displaystyle \sum_{e \in \pi} p(e) = k \cdot p(\pi) \end{align*}$$

Entonces, se dan las siguientes propiedades:

• Si $k > 0$ el camino de valor mínimo en $R$ es el mismo que en $R'$
• Si $k < 0$ el camino de valor mínimo en $R'$ es el camino de valor máximo en $R$

Camino de menor longitud

Este problema se puede reinterpretar como encontrar el camino de valor mínimo en una red orientada donde los pesos de los arcos valen 1, es decir, $p(e) = 1$ para cualquier $e \in A$.

A través de esta interpretación, podemos aplicar los algoritmos vistos anteriormente para encontrar caminos de menor longitud en una red orientada.

Caminos de menor valor entre todos los pares de vértices

Sea $R = (V, A, p)$ red orientada, se pretende calcular todos los caminos de menor valor entre todos los pares de vértices $i, j \in V$. Aunque una opción sería aplicar el algoritmo de Dijkstra $n$ veces, existe un algoritmo más eficiente conocido como el algoritmo de Floyd-Warshall.

Teorema 3.5. Algoritmo de Floyd-Warshall

Sea $R = (V, A, p)$ red orientada fuertemente conexa sin circuitos de valor negativo con $o(G) = n$ y $p(e) \in \mathbb{R}$ para cualquier $e \in A$ y sean:

$$\begin{align*} D_0(i,j) = \left\{ \begin{array}{ll} 0 & \text{ si } i = j\\ p_{ij} & \text{ si } (i,j) \in A\\ \infty & \text{ en otro caso} \end{array} \right. \qquad \text{y} \qquad I_0(i,j) = \left\{ \begin{array}{ll} i & \text{ si } i \neq j\\ - & \text{ en otro caso} \end{array} \right. \end{align*}$$

Y para cada $k \in \{1, \dots, n\}$ se definen:

$$\begin{align*} D_k(i, j) & = \min \left\{D_{k - 1}(i, j), D_{k - 1}(i, k) + D_{k - 1}(k, j)\right\}\\[2ex] I_k(i, j) & = \left\{ \begin{array}{ll} I_{k - 1}(i, j) & \text{ si } D_k(i, j) = D_{k - 1}(i, j)\\ I_{k - 1}(k, j) & \text{ si } D_k(i, j) \neq D_{k - 1}(i, j) \end{array} \right. \end{align*}$$

Se verifica que:

• $D_k(i, i) = 0$ representa el valor de un camino de menor valor de $i$ a $i$ tal que sus vértices intermedios pertenecen a $\{1, \dots, k\}$
• Si $i \neq j$ y $\exists \pi_{ij}$ con posibles vértices intermedios en $\{1, \dots, k\}$ entonces $D_k(i, j) \neq \emptyset$ representa el valor de un camino de menor valor de $i$ a $j$ tal que sus vértices intermedios pertenecen a $\{1, \dots, k\}$. Además, $I_k(i, j)$ representa el penúltimo vértice de dicho camino. Si no existe tal camino, entonces $D_k(i, j) = \infty$ y $I_k(i, j) = -$.

Corolario 3.6

Sea $R = (V, A, p)$ red orientada fuertemente conexa sin circuitos de valor negativo con $o(G) = n$ y $p(e) \in \mathbb{R}$ para cualquier $e \in A$. Entonces, para cualquier $i, j \in V$, $D_n(i, j)$ representa el valor de un camino de menor valor de $i$ a $j$ y $I_n(i, j)$ representa el penúltimo vértice de dicho camino. Si no existe tal camino, entonces $D_n(i, j) = \infty$ y $I_n(i, j) = -$.

Consecuencias del corolario 3.6

A partir del Corolario 3.6, se pueden extraer las siguientes consecuencias:

• De $I_n$ se obtienen todos los vértices de un camino de menor valor entre $i$ y $j$ aplicando el Teorema 3.2 de forma recursiva hacia atrás.
• De $D_n$ se obtiene el valor del camino de menor valor entre $i$ y $j$.
• Los caminos de menor valor desde un vértice $i$ se obtienen de las filas $i$-ésimas de las matrices $D_n$ e $I_n$.
• La información proporcionada en las filas es equivalente a la obtenida en la tabla resultante del algoritmo de Ford-Moore-Bellman aplicado desde la raíz de salida $i$.

Descripción del algoritmo de Floyd-Warshall

Sea $R = (V, A, p)$ red orientada fuertemente conexa con $o(G) = n$ y $p(e) \in \mathbb{R}$ para cualquier $e \in A$. El algoritmo de Floyd-Warshall se describe a continuación:

1. Definimos las matrices $D_0$ e $I_0$ como en el Teorema 3.5 y consideramos $k = 1$
2. Definimos los elementos de la matriz $D_k$ como:

$$\begin{align*} D_k(i, j) = \min \left\{D_{k - 1}(i, j), D_{k - 1}(i, k) + D_{k - 1}(k, j)\right\} \end{align*}$$

3. Obtenemos los elementos de la matriz $I_k$ como:

$$\begin{align*} I_k(i, j) = \left\{ \begin{array}{ll} I_{k - 1}(i, j) & \text{ si } D_k(i, j) = D_{k - 1}(i, j)\\ I_{k - 1}(k, j) & \text{ si } D_k(i, j) \neq D_{k - 1}(i, j) \end{array} \right. \end{align*}$$

4. Si $k < n$ entonces $k = k + 1$ y volvemos al paso 2. En otro caso, el algoritmo termina con las matrices $D_n$ e $I_n$.

Cadena de menor valor/longitud

Cadena de menor valor

Valor de una cadena. Definición

Sea $R = (V, A, p)$ red no orientada conexa, dados $i, j \in V$ y una cadena de $i$ a $j$ definida como:

$$\begin{align*} i \xleftrightarrow{p_{i, i_1}} i_1 \xleftrightarrow{p_{i_1, i_2}} i_2 \xleftrightarrow{p_{i_2, i_3}} \dots \xleftrightarrow{p_{i_{k-1}, i_k}} i_k \xleftrightarrow{p_{i_k, j}} j \end{align*}$$

El valor de la cadena se define como:

$$\begin{align*} \sum_{m = 0}^{k} p_{i_m, i_{m + 1}} = p_{i, i_1} + p_{i_1, i_2} + p_{i_2, i_3} + \dots + p_{i_{k-1}, i_k} + p_{i_k, j}\\ \end{align*}$$

Cadena de menor valor. Definición

Sea $R = (V, A, p)$ red no orientada conexa, dados $i, j \in V$, una cadena de menor valor de $i$ a $j$ es aquella cadena de $i$ a $j$ cuyo valor es mínimo entre todas las cadenas de $i$ a $j$.

Cadena de menor longitud

La idea de cadena de menor longitud es análoga a la de cadena de menor valor, pero en este caso, el peso de cada arista se considera como 1. Por tanto, el valor de una cadena coincide con su longitud, y la cadena de menor longitud entre dos vértices es aquella que tiene el menor número de aristas entre ellos.