Implementación del Algoritmo de Floyd para hallar el camino mas corto de un grafo

PLAIN TEXT
JAVA:
  1. /*
  2. John Edgar Congote Calle http://jcongote.blogspot.com
  3. */
  4.  
  5. import java.io.BufferedReader;
  6. import java.io.IOException;
  7. import java.io.InputStreamReader;
  8.  
  9. public final class Grafo {
  10.  
  11.     private int nnodos;
  12.  
  13.     private int nodos[][][];
  14.  
  15.     private char nombres[];
  16.  
  17.     Grafo(int n) {
  18.         this.nnodos = n;
  19.         this.nodos = new int[nnodos][nnodos][2];
  20.         this.nombres = new char[nnodos];
  21.     }
  22.  
  23.     public void ingresarArco(int n1, int n2, int peso) {
  24.         this.nodos[n1][n2][0] = peso;
  25.         this.nodos[n2][n1][0] = peso;
  26.         this.nodos[n1][n2][1] = n1;
  27.         this.nodos[n2][n1][1] = n2;
  28.     }
  29.  
  30.     public void ingresarNombre(int nodo, char letra) {
  31.         this.nombres[nodo] = letra;
  32.     }
  33.  
  34.     public void calcular() {
  35.         int i, j, k;
  36.         for (i = 0; i <this.nnodos; i++) {
  37.             for (j = 0; j <this.nnodos; j++) {
  38.                 for (k = 0; k <this.nnodos; k++) {
  39.                     if (this.nodos[i][k][0] + this.nodos[k][j][0] <this.nodos[i][j][0]) {
  40.                         this.nodos[i][j][0] = this.nodos[i][k][0]
  41.                                 + this.nodos[k][j][0];
  42.                         this.nodos[i][j][1] = k;
  43.                     }
  44.                 }
  45.             }
  46.         }
  47.     }
  48.  
  49.     public int pesominimo(int org, int des) {
  50.         return this.nodos[org][des][0];
  51.     }
  52.  
  53.     public String caminocorto(int org, int des) {
  54.         String cam;
  55.         if (org == des) {
  56.             cam = "->" + nombres[org];
  57.         } else {
  58.             cam = caminocorto(org, this.nodos[org][des][1]) + "->"
  59.                     + nombres[des];
  60.         }
  61.         return cam;
  62.     }
  63.  
  64.     public char getNombre(int nodo) {
  65.         return this.nombres[nodo];
  66.     }
  67.  
  68.     public static void main(String args[]) throws IOException {
  69.         Grafo g;
  70.  
  71.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  72.         String temp;
  73.         int res;
  74.  
  75.         System.out.println("Entre el numero de nodos del grafo:n");
  76.         temp = br.readLine();
  77.         res = Integer.parseInt(temp);
  78.  
  79.         g = new Grafo(res);
  80.  
  81.         for (int i = 0; i <res; i++) {
  82.             System.out.println("Cual es el nombre del nodo [" + (i + 1)
  83.                     + "]:n");
  84.             temp = br.readLine();
  85.             g.ingresarNombre(i, temp.charAt(0));
  86.         }
  87.         for (int i = 0; i <res; i++) {
  88.             for (int j = 0; j <res; j++) {
  89.                 if (i <j) {
  90.                     System.out.println("El nodo " + g.getNombre(i)
  91.                             + " esta conectado con el nodo " + g.getNombre(j)
  92.                             + " (s/n)n");
  93.                     temp = br.readLine();
  94.                     if (temp.charAt(0) == 's') {
  95.                         int peso;
  96.                         System.out.println("Cual es el peso del arco:n");
  97.                         temp = br.readLine();
  98.                         peso = Integer.parseInt(temp);
  99.                         g.ingresarArco(i, j, peso);
  100.                     } else {
  101.                         g.ingresarArco(i, j, 10000);
  102.                     }
  103.                 }
  104.             }
  105.         }
  106.  
  107.         g.calcular();
  108.         for (int i = 0; i <res; i++) {
  109.             for (int j = 0; j <res; j++) {
  110.                 if (i> j) {
  111.                     System.out.println("El camino mas corto entre los nodos:"
  112.                             + g.getNombre(i) + "-" + g.getNombre(j) + " es: n"
  113.                             + g.caminocorto(i, j) + " y su peso es: "
  114.                             + g.pesominimo(i, j));
  115.                 }
  116.             }
  117.         }
  118.     }
  119. }

Popularidad: 52%