Algoritmo de Floyd Warshall

Definicion:
   Sea G un grafo con m nodos, u 1 , u 2 , ..., u m suponga que queremos encontrar la matriz de caminos P para el grafo G. WARSHALL dio un algoritmo para este propósito que es mucho más eficiente que calcular las potencias de la matriz de adyacencia A y aplicar la proposición:

donde sea A la matriz de adyacencia y P = Pij la matriz de caminos de un grafo G entonces, Pij = 1 si y solo sí hay un numero positivo en la entrada ij de la matriz.

   El algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre 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.

Pseudo-codigo:

Floyd-Warshall (G)
n=|V [G]|
for (int i=1; i<=numeroNodos; i++)
  for (int j=1; j<=numeroNodos; j++)
      si Hay conexión   MatrizdePeso[i][j]=peso;
          else  MatrizdePeso[i][j]=infinito;
        MatrizNodoIntermedio[i][j]=j;
  Si i=j
      MatrizNodoIntermedio[i][j]=0;
      MatrizdePeso[i][j]=0;
 
for(int k=1;k<=numeroNodos;k++)
  for (int i=1;i<=numeroNodos;i++)
    for (int j=1;j<=numeroNodos;j++)
          a=MatrizdePeso[i][k]+MatrizdePeso[k][j];
       if(a<MatrizdePeso[i][j])
     {
     MatrizdePeso[i][j]=a;
     MatrizNodoIntermedio[i][j]=k;
     }
return MatrizdePeso, MatrizNodoIntermedio;

 Explicación:

     Dado un grafo G(V,A) se puede aplicar el algoritmo de Floyd para resolver el problema de encontrar el camino más corto de todos los vértices entre sí. 

Inicio
Armar la matriz de adyacencia F, teniendo en cuenta que F(i,j)=0 si i = j (diagonal principal es 0). Además dónde no exista camino se debe indicar con infinito.
Para k desde 1 hasta n
Para i desde 1 hasta n
Para j desde 1 hasta n
F[i,j]=min(F[i,j], F[i,k] + F[k,j])
Fin para j
Fin para i
Fin para k

En la k-esima vuelta F[i, j] contendrá el valor del camino más corto que una al vértice i con el j tal que dicho camino no pase por un vértice con número mayor que k.
La matriz resultante es la de los mínimos caminos entre cada nodo. Si se quiere saber cual es dicho camino, se debe armar un árbol a medida tomando como numero de nodo a k cada vez que se detecta que hubo una optimización.
Debido a su triple ciclo anidado es obviamente O(N^3).

Pronto se estará publicando la implementacion en pascal.