EJEMPLO DE IMPLEMENTACIÓN DEL ALGORITMO

Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias:

Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio.

1ª Iteración: nodo intermedio = 1

La matriz es simétrica, por lo que solamente hará falta calcular el triángulo superior de las distancias.

d₂₃ = min(d₂₃, d₂₁ + d₁₃) = 8

d₂₄ = min(d₂₄, d₂₁ + d₁₄) = 4

d₂₅ = min(d₂₅, d₂₁ + d₁₅) = 9

d₂₆ = min(d₂₆, d₂₁ + d₁₆) = 

d₃₂ = min(d₃₂, d₃₁ + d₁₂) = 8

d₃₄ = min(d₃₄, d₃₁ + d₁₄) = 6

d₃₅ = min(d₃₅, d₃₁ + d₁₅) = 7

d₃₆ = min(d₃₆, d₃₁ + d₁₆) = 1

d₄₅ = min(d₄₅, d₄₁ + d₁₅) = 

d₄₆ = min(d₄₆, d₄₁ + d₁₆) = 4

d₅₆ = min(d₅₆, d₅₁ + d₁₆) = 

La matriz de distancia después de esta iteración es:

2ª Iteración: nodo intermedio = 2

d₁₃ = min(d₁₃, d₁₂ + d₂₃) = 5

d₁₄ = min(d₁₄, d₁₂ + d₂₄) = 1

d₁₅ = min(d₁₅, d₁₂ + d₂₅) = 12

d₁₆ = min(d₁₆, d₁₂ + d₂₆) = 

d₃₄ = min(d₃₄, d₃₂ + d₂₄) = 6

d₃₅ = min(d₃₅, d₃₂ + d₂₅) = 7

d₃₆ = min(d₃₆, d₃₂ + d₂₆) = 1

d₄₅ = min(d₄₅, d₄₂ + d₂₅) = 13

d₄₆ = min(d₄₆, d₄₂ + d₂₆) = 4

d₅₆ = min(d₅₆, d₅₂ + d₂₆) = 

La matriz de distancia después de esta iteración es:

3ª Iteración: nodo intermedio = 3

d₁₂ = min(d₁₂, d₁₃ + d₃₂) = 3

d₁₄ = min(d₁₄, d₁₃ + d₃₄) = 1

d₁₅ = min(d₁₅, d₁₃ + d₃₅) = 12

d₁₆ = min(d₁₆, d₁₃ + d₃₆) = 6

d₂₄ = min(d₂₄, d₂₃ + d₃₄) = 4

d₂₅ = min(d₂₅, d₂₃ + d₃₅) = 9

d₂₆ = min(d₂₆, d₂₃ + d₃₆) = 9

d₄₅ = min(d₄₅, d₄₃ + d₃₅) = 13

d₄₆ = min(d₄₆, d₄₃ + d₃₆) = 4

d₅₆ = min(d₅₆, d₅₃ + d₃₆) = 8

La matriz de distancia después de esta iteración es:

4ª Iteración: nodo intermedio = 4

d₁₂ = min(d₁₂, d₁₄ + d₄₂) = 3

d₁₃ = min(d₁₃, d₁₄ + d₄₃) = 5

d₁₅ = min(d₁₅, d₁₄ + d₄₅) = 12

d₁₆ = min(d₁₆, d₁₄ + d₄₆) = 5

d₂₃ = min(d₂₃, d₂₄ + d₄₃) = 8

d₂₅ = min(d₂₅, d₂₄ + d₄₅) = 9

d₂₆ = min(d₂₆, d₂₄ + d₄₆) = 8

d₃₅ = min(d₃₅, d₃₄ + d₄₅) = 7

d₃₆ = min(d₃₆, d₃₄ + d₄₆) = 1

d₅₆ = min(d₅₆, d₅₄ + d₄₆) = 8

La matriz de distancia después de esta iteración es:

5ª Iteración: nodo intermedio = 5

d₁₂ = min(d₁₂, d₁₅ + d₅₂) = 3

d₁₃ = min(d₁₃, d₁₅ + d₅₃) = 5

d₁₄ = min(d₁₄, d₁₅ + d₅₄) = 1

d₁₆ = min(d₁₆, d₁₅ + d₅₆) = 5

d₂₃ = min(d₂₃, d₂₅ + d₅₃) = 8

d₂₄ = min(d₂₄, d₂₅ + d₅₄) = 4

d₂₆ = min(d₂₆, d₂₅ + d₅₆) = 8

d₃₄ = min(d₃₄, d₃₅ + d₅₄) = 6

d₃₆ = min(d₃₆, d₃₅ + d₅₆) = 1

d₄₆ = min(d₄₆, d₄₅ + d₅₆) = 4

La matriz de distancia después de esta iteración es:

6ª Iteración: nodo intermedio = 6

d₁₂ = min(d₁₂, d₁₆ + d₆₂) = 3

d₁₃ = min(d₁₃, d₁₆ + d₆₃) = 5

d₁₄ = min(d₁₄, d₁₆ + d₆₄) = 1

d₁₅ = min(d₁₅, d₁₆ + d₆₅) = 12

d₂₃ = min(d₂₃, d₂₆ + d₆₃) = 8

d₂₄ = min(d₂₄, d₂₆ + d₆₄) = 4

d₂₅ = min(d₂₅, d₂₆ + d₆₅) = 9

d₃₄ = min(d₃₄, d₃₆ + d₆₄) = 5

d₃₅ = min(d₃₅, d₃₆ + d₆₅) = 7

d₄₅ = min(d₄₅, d₄₆ + d₆₅) = 12

La matriz de distancia después de esta iteración es:

Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mínimo entre 2 vértices cualesquiera del grafo será el obtenido en la matriz final. En este caso, el camino mínimo entre 3 y 4 vale 5.


IMPLEMENTACION DEL ALGORITMO


package javaapplication15;

import javax.swing.JOptionPane;

/**
 *
 * @author Denis,lewis,johana
 */
public class JavaApplication15 {

    private int n;
    private int[][] A = new int[10][10];
    private int[] vect1 = new int[10];
    private int[] vect2 = new int[10];
    private int[][] B = new int[10][10];

    public void ingresar() {
        setN(Integer.parseInt(JOptionPane.showInputDialog(null, "Ingrese numero de nodos")));
        int i, j;
        for (i = 1; i <= getN(); i++) {
            for (j = 1; j <= getN(); j++) {
                getA()[i][j] = Integer.parseInt(JOptionPane.showInputDialog(null, "Ingrese la Matriz" + getA()[i][j]));
            }
        }
    }

    public void nodointer() {
        int i, j;
        for (i = 1; i <= 6; i++) {
            for (j = 1; j <= 6; j++) {
                if (i == j) {
                    getB()[i][j] = 0;
                } else {
                    getB()[i][j] = j;
                }
            }
        }
    }

    public void floid() {
        int bucle, i, j, suma;
        for (bucle = 1; bucle <= getN(); bucle++) {
            for (i = 1; i <= getN(); i++) {
                getVect1()[i] = getA()[bucle][i];
                getVect2()[i] = getA()[i][bucle];
            }
            for (i = 1; i <= getN(); i++) {
                for (j = 1; j <= getN(); j++) {
                    if (getVect2()[i] == 999 || getVect1()[j] == 999) {
                        suma = 999;
                    } else {
                        suma = getVect2()[i] + getVect1()[j];
                    }
                    if (suma < getA()[i][j]) {
                        getA()[i][j] = suma;
                        getB()[i][j] = bucle;
                    }
                }
            }
        }
    }

    public void mostrar1() {
        int i, j;
        JOptionPane.showInputDialog(null, "Imprime distancias o pesos optimo");
        for (i = 1; i <= getN(); i++) {
            for (j = 1; j <= getN(); j++) {
                JOptionPane.showMessageDialog(null, "Distancia es: " + getA()[i][j]);
            }
            JOptionPane.showMessageDialog(null, "\n\n");
        }
    }

    public void mostrar2() {
        int i, j;
        JOptionPane.showInputDialog(null, "Imprime matriz intermedios");
        for (i = 1; i <= getN(); i++) {
            for (j = 1; j <= getN(); j++) {
                JOptionPane.showMessageDialog(null, "Intermedios es:" + getB()[i][j]);
            }
            JOptionPane.showMessageDialog(null, "\n\n");
        }
    }

    public void preguntar() {
        int i, j;
        i = Integer.parseInt(JOptionPane.showInputDialog(null, "De que vertice a que vertice desea ir a: "));
        j = Integer.parseInt(JOptionPane.showInputDialog(null, "De que vertice a que vertice desea ir b: "));
        if (i == 0 || j == 0 || i == j) {
            JOptionPane.showMessageDialog(null, "Distancia minima es 0");
        } else {
            JOptionPane.showMessageDialog(null, "Distancia minima" + getA()[i][j] + "\n");
            JOptionPane.showMessageDialog(null, "Pasa por el: \t" + getB()[i][j] + "\t Y despues por el: \t" + j);
        }
    }

    public static void main(String[] args) {
        JavaApplication15 j = new JavaApplication15();
        j.ingresar();
        j.nodointer();
        j.floid();
        j.mostrar1();
        j.mostrar2();
        j.preguntar();

    }

    /**
     * @return the n
     */
    public int getN() {
        return n;
    }

    /**
     * @param n the n to set
     */
    public void setN(int n) {
        this.n = n;
    }

    /**
     * @return the A
     */
    public int[][] getA() {
        return A;
    }

    /**
     * @param A the A to set
     */
    public void setA(int[][] A) {
        this.A = A;
    }

    /**
     * @return the vect1
     */
    public int[] getVect1() {
        return vect1;
    }

    /**
     * @param vect1 the vect1 to set
     */
    public void setVect1(int[] vect1) {
        this.vect1 = vect1;
    }

    /**
     * @return the vect2
     */
    public int[] getVect2() {
        return vect2;
    }

    /**
     * @param vect2 the vect2 to set
     */
    public void setVect2(int[] vect2) {
        this.vect2 = vect2;
    }

    /**
     * @return the B
     */
    public int[][] getB() {
        return B;
    }

    /**
     * @param B the B to set
     */
    public void setB(int[][] B) {
        this.B = B;
    }
}