Algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall, explicado en 1959 por Bernard Roy, es un algoritmo de análisis de grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución.

Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos. La iteración se realiza sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba antes, y esto lo probamos con todos los nodos de la red. Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos.

Podemos definir caminoMinimo(i,j,k) de forma recursiva:

caminoMinimo(i,j,k) = min(caminoMinimo(i,j,k-1),caminoMinimo(i,k,k-1)+caminoMinimo(k,j,k-1));

caminoMinimo(i,j,0) = pesoArista(i,j);

Esta fórmula nos sirve como base del algoritmo Floyd-Warshall. Su funcion es ejecutar primero caminoMinimo(i,j,1) para todos los pares (i,j), así los usamos para después encontrar caminoMinimo(i,j,2) para todos los pares(i,j). El proceso continúa hasta que k = n, y que encontremos el camino más corto para todos los pares de vértices (i,j) usando algún vértice intermedio.

Pseudocódigo del algoritmo

Bueno aqui les dejo un pseudocódigo que vi en la internet y les quiero compartir.

/* Suponemos que la función pesoArista devuelve el coste del camino que va de i a j

    (infinito si no existe).

    También suponemos que n es el número de vértices y pesoArista(i,i) = 0

 */

 int camino[][];

 /* Una matriz bidimensional. En cada paso del algoritmo, camino[i][j] es el camino mínimo 

    de i hasta j usando valores intermedios de (1..k-1). Cada camino[i][j] es inicializado a 

    pesoArista(i,j)

 */

 procedimiento FloydWarshall ()

    para k: = 0 hasta n − 1

       para todo (i,j) en (0..n − 1)

          camino[i][j] = mín ( camino[i][j], camino[i][k]+camino[k][j]);

También les dejare estos vídeos que encontré donde te explica como encontrar las distancias mediante el algoritmo de Floyd-Warshall.

Esta es la primera parte

Esta es la segunda parte

Espero les sirva de ayuda estos vídeos como tutoriales, bueno esto sería todo.

Referencias:

Algoritmo de Floyd-Warshall