4.3.3. Problemas de caminos mínimos.
Problema de los caminos más cortos entre cualquier par de nodos:
Encontrar los caminos mínimos entre cualquier par de nodos.
Aplicar el algoritmo de Dijkstra N veces.
Podemos obtener la solución en O(n3) ó O((a+n)*n*log n).
Utiliza una matriz de adyacencia D[v, w], que será la matriz de costos.
Inicialmente D[v, w] contendrá los costos de las aristas C[v, w].
En cada paso k, en la posición D[v, w] estará la longitud del camino óptimo que pasa (posiblemente) por los k primeros nodos.
Al final del algoritmo, D almacenará los costos de los caminos mínimos.
En el paso k, el nodo k actúa de pivote. Calcular, para cada camino de v a w, si es más corto pasando por k.
- Dk[i, j]= min (Dk-1[i, j], Dk-1[i, k] + Dk-1[k, j]), para todo i?j.
- Dk[i, k]= min (Dk-1[i, k], Dk-1[i, k] + Dk-1[k, k]) ? la fila y la columna k no varían en el paso k, luego sólo necesitamos una matriz D.