Algoritmo Floyd Warshall

Introducción
El algoritmo de Floyd-Warshall es un algoritmo de análisis de grafos para que, de forma eficiente y simultanea, encuentre los caminos más cortos dentro de un grafo en el cual las aristas tengan un costo (distancia entre nodo y nodo, duración del viaje entre nodos, etc.). Al ejecutar el algoritmo encontrara el camino menor o mas corto de entre todos los pares de vértices, pero nodevuelve los detalles de los caminos en si. El algoritmo es un ejemplo de la Programación Dinámica y su variación mas conocida fue publicada en 1962 por Robert Floyd. Aunque es necesario comentar también que es esencialmente el mismo algoritmo descubierto independientemente y antes publicado por Bernard Roy en 1959 y por Stephen Warshall en 1962. De ahí sus múltiples pseudónimos: Algoritmo de Floyd,Algoritmo de Roy-Floyd, Algoritmo de Roy-Warshall, Algoritmo WFI. 
¿Como Funciona?
El algoritmo de Floyd-Warshall compara todos los posibles caminos entre cada par de nodos. Esto se consigue al ir mejorando un estimado de la distancia entre dos nodos, hasta que el estimado es optimo.
Considerar un grafo G con nodos o vertices V, cada una numerada de 1 a N, además de una función que al ingresari, j, k devuelve el camino mas corto entre i y j pasando solo por el conjunto {1, 2, …, k}. Ahora, utilizando esta función, el objetivo es encontrar el camino mas corto entre i para cada j usando solo los vértices 1 hasta k+1.
Existen dos candidatos para cada uno de esos caminos: o el verdadero camino mas corto pasando por los nodos {1, …, k}; o existe un camino que vaya desde i hasta k+1,después de k+1 hasta j que es mejor. Sabemos que el mejor camino de i a j que solo usa los nodos desde 1 hasta k esta definido por la función anterior, y esta claro que si existiera un camino desde i hasta k+1 hasta j, entonces el valor de este camino seria la concatenación de el camino mas corto de i hasta k+1 (usando vértices {1, …, k}) y el camino mas corto desde k+1 hasta j (también usando vértices{1, …, k}).
Si v(i,j) es el valor o costo de la arista entre los nodos i y j, podemos definir la función ahora llamada caminoCorto(i,j,k) en los términos de la siguiente formula recursiva: el caso base seria
caminoCorto(i,j,0) = v(i,j)
y el caso recursivo seria
caminoCorto(i,j,k)= min(caminoCorto(i,j,k-1), caminoCorto(i,k,k-1)+ caminoCorto(k,j,k-1)
Esta formula es el corazón del algoritmode Floyd-Warshall. El algoritmo funciona primero calculando la función para todos los pares (i,j) para k=1, después k=2, etc. Este proceso continua hasta k=n; y hemos encontrado el camino mas corto para todos los pares (i,j) usando cualquier nodo intermedio.
 
Pseudocódigo
Convenientemente, cuando se calcula el caso k, uno puede sobrescribir la información del calculo previo k-1.Reconstrucción del camino
El algoritmo de Floyd Warshall típicamente solo entrega los valores o costos de los caminos entre todos los pares de vértices. Con unas simples modificaciones, es posible crear un método para reconstruir el camino actual entre cualquier par de nodos. Mientras uno este inclinado a guardar el camino actual entre cada vértice a cada otro vértice, esto no es necesario, y dehecho, es muy castigador en términos de memoria. Para cada vértice uno simplemente necesita guardar la información sobre el nodo inmediato con el mayor índice que uno tiene que recorrer si uno desea terminar en cualquier otro índice, Por lo tanto, la informacion para reconstruir todos los caminos puede ser guardada en una matriz NxN “siguiente” donde siguiente[i][j] representa el vértice de mayoríndice que uno debe recorrer si uno intenta viajar por el camino mas corto desde i hasta j. implementar tal tipo de configuración es tan trivial como cuando se encuentra un nuevo camino mas corto, la matriz que contiene dicho camino se actualiza. La siguiente matriz es actualizada junto con la matriz de caminos de tal forma que la información de las dos tablas son completas y precisas, y...