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.
d23 =
min(d23, d21 + d13) = 8
d24 =
min(d24, d21 + d14) = 4
d25 =
min(d25, d21 + d15) = 9
d26 =
min(d26, d21 + d16) = 
d32 =
min(d32, d31 + d12) = 8
d34 =
min(d34, d31 + d14) = 6
d35 =
min(d35, d31 + d15) = 7
d36 =
min(d36, d31 + d16) = 1
d45 =
min(d45, d41 + d15) =
d46 =
min(d46, d41 + d16) = 4
d56 =
min(d56, d51 + d16) =
La
matriz de distancia después de esta iteración es:
2ª
Iteración: nodo intermedio = 2
d13 =
min(d13, d12 + d23) = 5
d14 =
min(d14, d12 + d24) = 1
d15 =
min(d15, d12 + d25) = 12
d16 =
min(d16, d12 + d26) =
d34 =
min(d34, d32 + d24) = 6
d35 =
min(d35, d32 + d25) = 7
d36 =
min(d36, d32 + d26) = 1
d45 =
min(d45, d42 + d25) = 13
d46 =
min(d46, d42 + d26) = 4
d56 =
min(d56, d52 + d26) =
La
matriz de distancia después de esta iteración es:
3ª
Iteración: nodo intermedio = 3
d12 =
min(d12, d13 + d32) = 3
d14 =
min(d14, d13 + d34) = 1
d15 =
min(d15, d13 + d35) = 12
d16 =
min(d16, d13 + d36) = 6
d24 =
min(d24, d23 + d34) = 4
d25 =
min(d25, d23 + d35) = 9
d26 =
min(d26, d23 + d36) = 9
d45 =
min(d45, d43 + d35) = 13
d46 =
min(d46, d43 + d36) = 4
d56 =
min(d56, d53 + d36) = 8
La
matriz de distancia después de esta iteración es:
4ª
Iteración: nodo intermedio = 4
d12 =
min(d12, d14 + d42) = 3
d13 =
min(d13, d14 + d43) = 5
d15 =
min(d15, d14 + d45) = 12
d16 =
min(d16, d14 + d46) = 5
d23 =
min(d23, d24 + d43) = 8
d25 =
min(d25, d24 + d45) = 9
d26 =
min(d26, d24 + d46) = 8
d35 =
min(d35, d34 + d45) = 7
d36 =
min(d36, d34 + d46) = 1
d56 =
min(d56, d54 + d46) = 8
La
matriz de distancia después de esta iteración es:
5ª
Iteración: nodo intermedio = 5
d12 =
min(d12, d15 + d52) = 3
d13 =
min(d13, d15 + d53) = 5
d14 =
min(d14, d15 + d54) = 1
d16 =
min(d16, d15 + d56) = 5
d23 =
min(d23, d25 + d53) = 8
d24 =
min(d24, d25 + d54) = 4
d26 =
min(d26, d25 + d56) = 8
d34 =
min(d34, d35 + d54) = 6
d36 =
min(d36, d35 + d56) = 1
d46 =
min(d46, d45 + d56) = 4
La
matriz de distancia después de esta iteración es:
6ª
Iteración: nodo intermedio = 6
d12 =
min(d12, d16 + d62) = 3
d13 =
min(d13, d16 + d63) = 5
d14 =
min(d14, d16 + d64) = 1
d15 =
min(d15, d16 + d65) = 12
d23 =
min(d23, d26 + d63) = 8
d24 =
min(d24, d26 + d64) = 4
d25 =
min(d25, d26 + d65) = 9
d34 =
min(d34, d36 + d64) = 5
d35 =
min(d35, d36 + d65) = 7
d45 =
min(d45, d46 + d65) = 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;
}
}
