EXPLICACION DEL ALGORITMO

El algoritmo de Floyd-Warshall compara todos los posibles caminos entre cada par de nodos. Esto se consigue al ir mejorando un estimado de la distancia entre dos nodos, hasta que el estimado es óptimo.
Considerar un grafo G con nodos o vértices V, cada una numerada de 1 a N, ad más de una función que al ingresar i, j, k devuelve el camino más corto entre i y j pasando solo por el conjunto {1, 2,…, k}. Ahora, utilizando esta función, el objetivo es encontrar el camino más corto entre i para cada j usando solo los vértices 1 hasta k+1.
Existen dos candidatos para cada uno de esos caminos: o el verdadero camino más corto pasando por los nodos {1,…, k}; o existe un camino que vaya desde i hasta k+1, después de k+1 hasta j que es mejor. Sabemos que el mejor camino de i a j que solo usa los nodos desde 1 hasta k está definido por la función anterior, y está claro que si existiera un camino desde i hasta k+1 hasta j, entonces el valor de este camino seria la concatenación de el camino más corto de i hasta k+1 (usando vértices {1,…, k}) y el camino más corto desde k+1 hasta j (también usando vértices {1,…, k}).
Si v(i,j) es el valor o costo de la arista entre los nodos i y j, podemos definir la función ahora llamada camino Corto(i,j,k) en los términos de la siguiente formula recursiva: el caso base seria 
camino Corto(i,j,0) = v(i,j)
y el caso recursivo seria
camino Corto(i,j,k)= min(camino Corto(i,j,k-1), camino Corto(i ,k,k-1)+ camino Corto(k,j,k-1)
Esta fórmula es el corazón del algoritmo de Floyd-Warshall. El algoritmo funciona primero calculando la función para todos los pares (i,j) para k=1, después k=2, etc. Este proceso continua hasta k=n; y hemos encontrado el camino más corto para todos los pares (i, j) usando cualquier nodo intermedio.

ALGORITMO


package javaapplication16;

import java.util.Scanner;

/**
 *
 * @author Denis,Lewis,Johna
 */
public class JavaApplication16 {

    public static int[][] shortestpath(int[][] adj, int[][] path) {

        int n = adj.length;
        int[][] ans = new int[n][n];

        // Implementar el algoritmo en una matriz de copia de modo que la adyacencia no es
        //destruido.
        copy(ans, adj);

        // Calcular rutas sucesivamente a través de una mejor k vértices.
        for (int k = 0; k < n; k++) {

            // Es así que entre cada par de puntos posibles.
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {


                    if (ans[i][k] + ans[k][j] < ans[i][j]) {
                        ans[i][j] = ans[i][k] + ans[k][j];
                        path[i][j] = path[k][j];
                    }
                }
            }
        }

        // Devuelva la matriz camino más corto.
        return ans;
    }

    //Copia el contenido del array b en un array. Se asume que tanto a como
    //B es una matriz 2D de dimensiones idénticas.
    public static void copy(int[][] a, int[][] b) {

        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                a[i][j] = b[i][j];
            }
        }
    }

    // Devuelve el menor de a y b.
    public static int min(int a, int b) {
        if (a < b) {
            return a;
        } else {
            return b;
        }
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);

        // Pruebas fuera con algoritmo gráfico mostrado en clase.
        int[][] m = new int[5][5];
        m[0][0] = 0;
        m[0][1] = 3;
        m[0][2] = 8;
        m[0][3] = 10000;
        m[0][4] = -4;
        m[1][0] = 10000;
        m[1][1] = 0;
        m[1][2] = 10000;
        m[1][3] = 1;
        m[1][4] = 7;
        m[2][0] = 10000;
        m[2][1] = 4;
        m[2][2] = 0;
        m[2][3] = 10000;
        m[2][4] = 10000;
        m[3][0] = 2;
        m[3][1] = 10000;
        m[3][2] = -5;
        m[3][3] = 0;
        m[3][4] = 10000;
        m[4][0] = 10000;
        m[4][1] = 10000;
        m[4][2] = 10000;
        m[4][3] = 6;
        m[4][4] = 0;

        int[][] shortpath;
        int[][] path = new int[5][5];

        // Inicializar con el vértice anterior para cada borde. -1 indica
        // no tal vertice.
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (m[i][j] == 10000) {
                    path[i][j] = -1;
                } else {
                    path[i][j] = i;
                }
            }
        }

        // Esto significa que no tiene que ir a ninguna parte para ir de i a i.
        for (int i = 0; i < 5; i++) {
            path[i][i] = i;
        }

        shortpath = shortestpath(m, path);

        // Imprime distancias más cortas.
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                System.out.print(shortpath[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("De dónde a dónde usted quiere encontrar el camino más corto?(0 to 4)");
        int start = stdin.nextInt();
        int end = stdin.nextInt();

        // La ruta finalizará siempre en fin.
        String myPath = end + "";

        // Recorrer cada vértice anterior hasta que vuelvas a empezar.
        while (path[start][end] != start) {
            myPath = path[start][end] + " -> " + myPath;
            end = path[start][end];
        }

        // Sólo tiene que añadir comienzo de nuestra cadena y de impresión.
        myPath = start + " -> " + myPath;
        System.out.println("Este es el camino " + myPath);
        // TODO code application logic here
    }
}