All pairs Shortest paths - Algoritmo de la multiplicación de Matrices

Definamos $W=(w_{ij})$, la matrix de pesos del Grafo $G=(V,E)$ supongamos que $G$ no tiene Ciclos negativos. El problema de encontrar los caminos mas cortos para cualquier par de vertices

de el Grafo $G$ tiene como salida (output) una matrix $D =(d_{ij})$ donde $d_{ij}$ es el peso del camino mas corto desde el vertices $i$ al $j$, en este articulo veremos un primer algoritmos que se asemeja mucho al del multiplicación de matrices.

Este algoritmo, para solucionar el problema, utiliza el paradigma de programación dinámica.

• Caracterización de la subestructura optima, Consideremos que el camino $p$ de $i$ a $j$ que tiene a lo mas $m$ aristas. Como $G$ no tiene Ciclos negativos $m < \infty$, si $i=j$ entonces $w(p)=0$ y $p$ no tiene aristas, si $i \neq j$ entonces podemos descomponer $p$ en camino que va a un $k$ predecesor de $j$ en $p$, el camino de $i$ a $k$ es el camino mas corto de $i$ a $k$ ya que $p$ lo es de $i$ a $j$
• Sea $l_{ij} ^{(m)}$ el mínimo peso de un camino de $i$ a $j$ que tiene a lo mas $m$ aristas, cuando $m=0$ existe un camino si y solo si $i=j$.

$l_{ij}=\left\{\begin{array}{cc} 0 & i=j\\ \infty & i\neq j \end{matrix}$

Para $m \geq 1$ $l_{ij}^m$ es el mínimo entre $l_{ij} ^{m-1}$ y el peso de cualquier camino que tenga a lo mas $m$ aristas obtenidos a observar todos los posibles predecesores $k$ de $j$.

$\begin{array}{ll} l_{ij}^{(m)} &=min(l_{ij}^{(m-1)},min_k\{l_{ik} ^{(m-1)} + w_{kj}\}) \\ & =min_k\{l_{ik} ^{(m-1)} + w_{kj}\} \end{array}$

La ultima igualdad se tiene ya que $w _{jj}=0$ para todo $j$.

Como $G$ no tiene Ciclos entonces el camino mas corto de $i$ a $j$ es simple tendrá en el peor de los casos $n-1$ aristas ósea.

$$\delta(ij)=l_{ij} ^{n-1} = l_{ij} ^n = \cdots$$

• Computemos la serie de matrices $L ^{(1)},L ^{(2)},\ldots ,L ^{(n-1)}$ donde $L ^{(m)}=(l_{ij}^{m})$, la matrix final $L ^{(n-1)}$ contiene los pesos de los caminos mas cortos para cada par $ij$, observe que $L ^{(1)}=W$, el corazón del algoritmo es el siguiente procedimiento llamado:

EXTEND-SHORTED-PATHS que tiene como entrada una matrix $L ^{(m-1)}$ y $W$ y retorna $L ^{(m)}$

ESTEND-SHORTED-PATHS(L,W)

1. $N\leftarrow rows[L]$

2. $L'=(l'_{ij})$

3. for $i \leftarrow 1$ to $n$

4 . do for $j \leftarrow 1$ to $n$

5. do $l' _{ij} \leftarrow \infty$

6. for $k \leftarrow 1$ to $n$

7. do $l' _{ij} \leftarrow min(l' _{i,j}, l_{ij} +w _{kj})$

8 return $L'$

Este procedimiento se escribe sin superíndice para hacer la entrada y la salida independiente de $m$, es claro que este procedimiento pertenece al orden de $O(n^3)$ y si calculamos una a una las matrices $L ^{(m)}$ nos tomara un tiempo de orden $O(n^4)$ lo que es muy costoso, veamos la relación que hay entre este procedimiento y el de multiplicación de matrices. Para calcular la matrix $C=A \cdot B$ tendremos que calcular para todo par $i,j=1,2,\ldots ,n$.

$$c_{ij}=\sum _{k=1} ^{n} a_{ik} \cdot b_{kj}$$

Si hacemos la siguiente sustitución y definimos un semianillo.

$$\begin{array}{cc}+ &\rightarrow min \\ \cdot & + \end{array}$$

podemos redefinir el algoritmo de la multiplicación de matrices calculando cada elemento de la matrix producto como $min_k\{l_{ik} ^{(m-1)} + w_{kj}\})$ teniendo como la matrix identidad:

$$L ^{(0)}=I= \left (\begin{array}{cccc} 0 & \infty & \cdots & \infty \\ \infty & 0 & \cdots & \infty \\ \vdots & \vdots & \ddots & \vdots \\ \infty & \infty & \cdots & 0 \end{array}\right) $$

Gracias a esto podemos calcular las "potencias" $L ^{(m)}$ no de una en una sino en potencias de dos hasta $m=2^{\lfloor lg (n-1) \rfloor} $ya que $\delta(ij)=l_{ij} ^{n-1} = l_{ij} ^n = \cdots$,y con esto disminuir el numero de iteraciones de $O(n^4)$ a $O(n^3lg n)$