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)$
