Algoritmo de Floyd.

Definición según "Wikipedia".


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 V³ comparaciones (esto es notable considerando que puede haber hasta V² 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 1 hasta 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 + 1hasta 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 + 1 a 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)).

Esta fórmula es la base del algoritmo Floyd-Warshall. Funciona ejecutando primero caminoMinimo(i,j,1) para todos los pares (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.

Ejercicio Práctico.

Implementar en Java el algoritmo de Floyd para obtener los caminos mas cortos entre todos los pares de nodos de un grafo (no) dirigido valorado. Se implementa fuera de cualquier clase que implemente grafos, y no usa ninguno de sus métodos. Suponermos que los vértices del grafo contienen su número de orden 0, 1, 2, ..., n-1.

El prototipo del método debe ser:

public static int[][] Floyd(int[][] ady)

donde ady es la matriz de adyacencias, que inicialmente contiene el valor de las aristas (o el valor infinito Integer.MAX_VALUE si no existe arista) y, tras la ejecución del método, contendrá las distancias de los caminos mas cortos.
La matriz devuelta contiene los caminos óptimos en forma de nodos de paso; es decir, si la posición [i][j] vale k, el mejor camino para ir desde i hasta j pasa por el vértice k (si k==j, se trata de una arista, y si [i][j] vale infinito no existe camino).

Debe implementarse también el método:

public static Lista camino(int i, int j, int[][] caminos)

para construir todo el camino desde i hasta j, a partir de una matriz de caminos como la obtenida por el método anterior.
Por ejemplo, para el grafo (copiar y pegar para hacer pruebas):

int inf = Integer.MAX_VALUE; // infinito

int[][] a =
{ {inf, 9, 20, 4, inf, inf},
{ 9, inf, inf, inf, 1, inf},
{ 20, inf, inf, inf, inf, 5},
{ 4, inf, inf, inf, inf, 0},
{inf, 1, inf, inf, inf, 3},
{inf, inf, 5, 0, 3, inf}
};
// si conviene, la diagonal puede contener 0's en vez de inf's

si hacemos la llamada:

int[][] caminos = Floyd(a);

int d = caminos.length;

for (int i=0; i
se obtine:

camino desde 0 hasta 1: (0, 3, 5, 4, 1) distancia = 8
camino desde 0 hasta 2: (0, 3, 5, 2) distancia = 9
camino desde 0 hasta 3: (0, 3) distancia = 4
camino desde 0 hasta 4: (0, 3, 5, 4) distancia = 7
camino desde 0 hasta 5: (0, 3, 5) distancia = 4
camino desde 1 hasta 2: (1, 4, 5, 2) distancia = 9
camino desde 1 hasta 3: (1, 4, 5, 3) distancia = 4
camino desde 1 hasta 4: (1, 4) distancia = 1
camino desde 1 hasta 5: (1, 4, 5) distancia = 4
camino desde 2 hasta 3: (2, 5, 3) distancia = 5
camino desde 2 hasta 4: (2, 5, 4) distancia = 8
camino desde 2 hasta 5: (2, 5) distancia = 5
camino desde 3 hasta 4: (3, 5, 4) distancia = 3
camino desde 3 hasta 5: (3, 5) distancia = 0
camino desde 4 hasta 5: (4, 5) distancia = 3

(las soluciones no son únicas, salvo las distancias).

________________________________________________________________________

Solución:

#include 

public static int[][] Floyd(int[][] ady){

   // se inicializa con las aristas.
   int[][] resultado = new int[ady.length][ady.length];

   for (int i = 0; i < ady.length; i++)
      for (int j = 0; j < ady.length; j++)

         resultado[i][j] = j;

   //Algoritmo de Floyd
   // si el camino desde i a j es mejor al meter k
   // se actualiza las matrices
   
   for (int k = 0; k < ady.length; k++){
      for (int i = 0; i < ady.length; i++){
         for (int j = 0; j < ady.length; j++){

            if ((ady[i][k] != Integer.MAX_VALUE)&&(ady[k][j] != Integer.MAX_VALUE)&&(Math.min(ady[i][j], ady[i][k] + ady[k][j]) != ady[i][j])){

				ady[i][j] = ady[i][k] + ady[k][j];
				resultado[i][j] = resultado[i][k];
            }
         }
      }
   }

   return resultado;
}

//construye el camino desde i hasta j, a partir de una matriz de caminos como la obtenida por el método anterior.
public static Lista camino(int i, int j, int[][] caminos){

   if (i == j)
      return new Lista_Dinamica(j, new Lista_Dinamica());

   Lista lista = camino(i, caminos[j][i], caminos);
   
   lista.Concatena(new Lista_Dinamica(j, new Lista_Dinamica()));
   
   return lista;
}

<\pre>