Algoritmo de Floyd-Warshall

En informática, 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. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica.

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.

La siguiente es una implementación en código C del algoritmo de Floyd-Warshall para la solución de todos los pares de la menor problema del camino.
Código en C++

//resuelve todos los pares de la menor problema del camino utilizando el algoritmo de Floyd-Warshall

void fwarsh(int nn, double *cmat, double **dist_mat, int **pred_mat)
{
  double *dist;
  int *pred;
  int i,j,k; / / bucle de contadores

   / / inicializar las estructuras de datos
  dist = (double *)malloc(sizeof(double) * nn * nn);
  pred = (int *)malloc(sizeof(int) * nn * nn);
  memset(dist, 0, sizeof(double)*nn*nn);
  memset(pred, 0, sizeof(int)*nn*nn);

 / / algoritmo de inicialización
  for (i=0; i < nn; i++) {
    for (j=0; j < nn; j++) {
      if (cmat[i*nn+j] != 0.0)
 dist[i*nn+j] = cmat[i*nn + j];
      else
 dist[i*nn+j] = HUGE_VAL; / / desconectado
      if (i==j)  / / caso diagonal
 dist[i*nn+j] = 0;

      if ((dist[i*nn + j] > 0.0) && (dist[i*nn+j] < HUGE_VAL))
 pred[i*nn+j] = i;
    }
  }
 
  / / Bucle principal del algoritmo
  for (k=0; k < nn; k++) {
    for (i=0; i < nn; i++) {
      for (j=0; j < nn; j++) {
 if (dist[i*nn+j] > (dist[i*nn+k] + dist[k*nn+j])) {
   dist[i*nn+j] = dist[i*nn+k] + dist[k*nn+j];
   pred[i*nn+j] = k; 
   //printf("actualiza la entrada %d,%d with %d\n", i,j, dist[i*nn+j]);
 }
      }
    }
  }

   / * / / Imprime la tabla de resultados de las distancias más cortas
  for (i=0; i < nn; i++) {
    for (j=0; j < nn; j++)
      printf("%g ", dist[i*nn+j]);
    printf("\n");
    } */
  
   / / ahora el conjunto de matrices y dist pred para la función de llamada
   / / pero algunos controles porque permitimos que se pasa NULL si el usuario
   / / no se preocupa por uno de los resultados.
  if (dist_mat)
    *dist_mat = dist;
  else
    free(dist);

  if (pred_mat)
    *pred_mat = pred;
  else
    free(pred);

  return;
}  //Fin de fwarsh()

// Declaraciones en el archivo .h
int cn; //cantidad de nodos
vector< vector<int> > ady; //matriz de adyacencia
 
// Devuelve una matriz con las distancias minimas de cada nodo al resto de los vertices.
vector< vector<int> > Grafo :: floyd(){
    vector< vector<int> > 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;
}

• Obtiene la mejor ruta entre todo par de nodos.
• Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos.

• La iteración se produce 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 anteriormente, y esto se prueba 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.

Es decir el algoritmo es el siguiente:
Iniciación.
- matriz de distancias.
- distancia del enlace entre el nodo i y el nodo j.
Iteración. Para n=0,1 ... ,N-1

Empezando con el nodo 1 como intermedio (n=0), se prueba con todos los nodos como nodos intermedios, el último es con el nodo N como nodo intermedio (n=N-1), y así se van hallando las distancias mínimas.


http://pier.guillen.com.mx/algorithms/10-graficas/10.5-floyd.htm
http://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall
www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/.../shortest_path.html