EXPLICACION DEL ALGORITMO

El algoritmo de Floyd es más general que el de Dijkstra, ya que determina la ruta más corta entre dos nodos cualquiera de la red.

• El algoritmo representa una red de n nodos como una matriz cuadrada de orden n, la llamaremos matriz C. De esta forma, el valor Cijrepresenta el coste de ir desde el nodo i al nodo j, inicialmente en caso de no existir un arco entre ambos, el valor Cij será infinito.
• Definiremos otra matriz D, también cuadrada de orden n, cuyos elementos van a ser los nodos predecesores en el camino hacia el nodo origen, es decir, el valor Dij representará el nodo predecesor a j en el camino mínimo desde i hasta j. Inicialmente se comienza con caminos de longitud 1, por lo que Dij = i.
• Las diagonales de ambas matrices representan el coste y el nodo predecesor para ir de un nodo a si mismo, por lo que no sirven para nada, estarán bloqueadas.

Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes: 

• Formar las matrices iniciales C y D.
• Se toma k=1.
• Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i≠k, j≠k e i≠j, hacemos:

Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj

En caso contrario, dejamos las matrices como están. 

• Si k ≤ n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario paramos las iteraciones.
• La matriz final C contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz D contiene los penúltimos vértices de los caminos óptimos que unen dos vértices, lo cual permite reconstruir cualquier camino óptimo para ir de un vértice a otro.

codigo de algoritmo floyd

import java.io.*;

public class Floyd

{

static int [ ][ ]floyd;

static BufferedReader leer=new BufferedReader(new InputStreamReader(System.in));

public static void main()

{

int n=0;

try {

System.out.print(“Ingrese n (tamaño de la matriz n X n) : “);

n=Integer.parseInt(leer.readLine());

floyd=new int[n][n];

for (int i=0;i<n;i++)

for (int j=0;j<n;j++)

{

System.out.println(“Inserte la componente W(” + i + “)(” + j +”)”);

floyd[i][j]=Integer.parseInt(leer.readLine());

}

}

catch(Exception e){}

for (int k=0;k<=n-1;k++)

{

for (int i=0;i<=n-1;i++)

{for (int j=0;j<=n-1;j++)

if ((floyd[i][k]!=-1)&&(floyd[k][j]!=-1))

floyd[i][j]=funcionfloyd(floyd[i][j],floyd[i][k]+floyd[k][j]);}

}

System.out.println(“Matriz de adyacencia correspondiente: “);

for (int i=0;i<n;i++)

{

for (int j=0;j<n;j++)

System.out.print(” – “+floyd[i][j]);

System.out.println();

}

}

public static int funcionfloyd(int A, int B)

{

if ((A==-1)&&(B==-1))

return -1;

else if (A==-1)

return B;

else if (B==-1)

return A;

else if (A>B)

return B;

else return A;

}      }