ALGORITMO DE FLOYD JAVA

En algunas aplicaciones resulta interesante determinar el camino mínimo entre todos los pares
de vértices de un grafo dirigido y valorado. Considerando como vértice origen cada uno de los
vértices del grafo, el algoritmo de Dijkstra resuelve el problema. Existe otra alternativa, más
elegante y más directa, propuesta por Floyd que recibe el nombre de algoritmo de Floyd.
El grafo, de nuevo, está representado por la matriz de pesos, de tal forma que todo arco
(vi,vj) tiene asociado un peso cij; si no existe arco, cij = ∞. Además, cada elemento de la
diagonal, cii, se hace igual a 0. El algoritmo de Floyd determina una nueva matriz, D, de n x n
elementos tal que cada elemento, Dij, contiene el coste del camino mínimo de vi a vj .
El algoritmo tiene una estructura similar al algoritmo de Warshall para encontrar la matriz de
caminos. Se generan consecutivamente las matrices D1, D2, ..., Dk, ... , Dn a partir de la matriz
Do que es la matriz de pesos. En cada paso se incorpora un nuevo vértice y se estudia si con ese
vértice se puede mejorar los caminos para ser más cortos. El significado de cada matriz es:
D0[i,j] = cij coste (peso) del arco del vértice i al vértice j
∞ si no hay arco.

D1[i,j] = minimo(D0[i,j],D0[i,1]+D0[1,j]).
Menor de los costes entre el anterior camino mínimo de i a j y la suma de costes
de caminos de i a 1 y de 1 a j.
D2[i,j] = minimo(D1[i,j],D1[i,2]+D1[2,j]).
Menor de los costes entre el anterior camino mínimo de i a j y la suma de los
costes de caminos de i a 2 y de 2 a j.
En cada paso se incorpora un nuevo vértice para determinar si hace el camino menor entre
un par de vértices.
Dk[i,j] = minimo(Dk-1[i,j],Dk-1[i,k]+Dk-1[k,j]).
Menor de los costes entre el anterior camino mínimo de i a j y la suma de los
costes de caminos de i a k y de k a j.
De forma recurrente, se añade en cada paso un nuevo vértice para determinar si se consigue
un nuevo camino mínimo, hasta llegar al último vértice y obtener la matriz Dn, que es la matriz
de caminos mínimos del grafo.

Se define la clase TodoCaminoMinimo para implentar el algoritmo al que se añade un pequeño
cambio: guardar, en la matriz traza, el índice del último vértice que ha hecho que el camino
sea mínimo desde el vértice vi al vj, para cada par de vértices del grafo.
package Grafo;
public class TodoCaminoMinimo
{
private int [][] pesos;
private int [][] traza;
private int [][] d;
private int n; // número de vértices
public TodoCaminoMinimo(GrafMatPeso gp)
{
n = gp.numeroDeVertices();
pesos = gp.matPeso;
d = new int [n][n];
traza = new int [n][n];
}
public void todosCaminosMinimo()
{
// matriz inicial es la de pesos.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
d[i][j] = pesos[i][j];
traza[i][j] = -1; // indica que camino mas corto es el arco
}

// Camino mínimo de un vértice a si mismo: 0
for (int i = 0; i < n; i++)
d[i][i] = 0;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if ((d[i][k] + d[k][j]) < d[i][j]) // nuevo mínimo
{
d[i][j] = d[i][k] + d[k][j];
traza[i][j]= k;
}
}
}