Algoritmo de floy grafos

Algoritmo
El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo V3 comparaciones (esto es notable considerando que puede haber hasta V2 aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices,hasta que se sabe que la estimación es óptima.
Sea un grafo G con conjunto de vértices V, numerados de 1 a N. Sea además una función caminoMinimo(i,j,k) que devuelve el camino mínimo de i a j usando únicamente los vértices de 1 a k como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino mínimo desde cada i a cada j usando únicamente los vértices de 1hasta k + 1.
Hay dos candidatos para este camino: un camino mínimo, que utiliza únicamente los vértices del conjunto (1...k); o bien existe un camino que va desde i hasta k + 1, después de k + 1 hasta j que es mejor. Sabemos que el camino óptimo de i a j que únicamente utiliza los vértices de 1 hasta k está definido por caminoMinimo(i,j,k), y está claro que si hubiera un camino mejor de i a k + 1a j, la longitud de este camino sería la concatenación del camino mínimo de i a k + 1 (utilizando vértices de (1...k)) y el camino mínimo de k + 1 a j (que también utiliza los vértices en (1...k)).

Por lo tanto, podemos definir caminoMinimo(i,j,k) de forma recursiva:


Esta fórmula es la base del algortimo Floyd-Warshall. Funciona ejecutando primero caminoMinimo(i,j,1) para todos lospares (i,j), usándolos para después hallar caminoMinimo(i,j,2) para todos los pares (i,j)... Este proceso continúa hasta que k = n, y habremos encontrado el camino más corto para todos los pares de vértices (i,j) usando algún vértice intermedio.
[editar] Pseudocodigo
Convenientemente, cuando calculamos el k-esimo caso, se puede sobreescribir la información salvada en la computación k -1. Estosignifica que el algoritmo usa memoria cuadrática. Hay que cuidar la inicialización de las condiciones:
1 /* Suponemos que la función pesoArista devuelve el coste del camino que va de i a j
2 (infinito si no existe).
3 También suponemos que n es el número de vértices y pesoArista(i,i) = 0
4 */
5
6 int camino[][];
7 /* Una matriz bidimensional. En cada paso del algoritmo, camino[i][j] es elcamino mínimo
8 de i hasta j usando valores intermedios de (1..k-1). Cada camino[i][j] es inicializado a
9 pesoArista(i,j)
10 */
11
12 procedimiento FloydWarshall ()
13 para k: = 0 hasta n − 1
14 para todo (i,j) en (0..n − 1)
15 camino[i][j] = mín ( camino[i][j], camino[i][k]+camino[k][j]);
[editar] Código en C++
// Declaraciones en el archivo .h
int cn;//cantidad de nodos
vector< vector > ady; //matriz de adyacencia

// Devuelve una matriz con las distancias minimas de cada nodo al resto de los vertices.
vector< vector > Grafo :: floyd(){
vector< vector > path = this->ady;

for(int i = 0; i < cn; i++)
path[i][i] = 0;

for(int k = 0; k < cn; k++)
for(int i = 0; i < cn; i++)
for(int j = 0; j < cn;j++){
int dt = path[i][k] + path[k][j];
if(path[i][j] > dt)
path[i][j] = dt;
}

return path;
}
[editar] Comportamiento con ciclos negativos
Para que haya coherencia numérica, Floyd-Warshall supone que no hay ciclos negativos (de hecho, entre cualquier pareja de vértices que forme parte de un ciclo negativo, el caminomínimo no está bien definido porque el camino puede ser infinitamente pequeño). No obstante, si hay ciclos negativos, Floyd-Warshall puede ser usado para detectarlos. Si ejecutamos el algoritmo una vez más, algunos caminos pueden decrementarse pero no garantiza que, entre todos los vértices, caminos entre los cuales puedan ser infinitamente pequeños, el camino se reduzca. Si los números de la...