Dijkstra en java

[- English -]

El algorítmo de Dijkstra es parte de la teoría de grafos. Este algorítmo esta hecho para encontrar el camino más corto de un punto dado [nodo] hacia otro punto dentro de un grafo ponderado y dirigido.

Un grafo ponderado y dirigido es aquel cuyos nodos estan conectados por aristas que tienen un peso o ponderación, llamado costo, y cada arista es unidireccional. Como el mostrado en la figura siguiente:




En el grafo anterior podemos observar que para ir del nodo A al C hay una arista, camino, con un costo de 3, pero para ir del nodo A al E no hay un camino directo sino que se debe pasar a través de otros nodos, la cuestión es ¿Cuál opción tendrá el costo más bajo? ¿Ir a traves del nodo B, D o C?

Resolver la cuestion descrita en forma programatica se hace implementando el algorítmo de Dijkstra.

La forma en que lo he implementado se basa en representar el grafo en una matriz de adyacencia, donde los costos se colocan en una matriz de NxN siendo N el numero de nodos y donde cada reglon en conjunción con su columna representa la dirección del costo indicado. El grafo de la figura se convierte a matriz de adyacencia y queda así:

A B C D E
A -1 10 3 8 -1
B 4 -1 -1 1 4
C -1 2 -1 -1 -1
D -1 -1 2 -1 -1
E 5 -1 -1 5 -1

Las direcciones de las aristas se consideran desde el nodo reglon (marcado en azul) hacia el nodo columna (marcado en negro), por lo tanto si vemos del nodo A (azul) al B (negro) hay un costo de 10 y se corresponde con el grafo. Los valores marcados en rojo (-1) indican que no hay arista o que es un lazo, un lazo es un ciclo de un nodo a si mismo, ejemplo desde C hacia C.

El programa lo hice en modo consola y puede leer los datos de las aristas uno por uno o toda la matriz desde una archivo de texto simple, la matriz anterior en un archivo de texto se ha de guardar sólo los valores, separados por un espacio, sin cabeceras de columna ni reglon, así:

-1 10 3 8 -1
4 -1 -1 1 4
-1 2 -1 -1 -1
-1 -1 2 -1 -1
5 -1 -1 5 -1

La ejecucion y salida desde consola (usando el grafo de la figura) se ve así:
..[linea de comandos]..>java principal Implementacion del algoritmo de Dijkstra Numero de nodos que tiene el grafo a resolver?
5 * Ingresa el numero de opcion para cargar el grafo: 1=Desde teclado 2=Desde archivo (El archivo debe ser de texto simple y estar
formado por una matriz de nxn donde: n=numero de nodos y debe ser una matriz de adyacencia con la siguientes caracteristicas: las
aristas existentes se representaran por su costo, las no existentes y lazos por -1) 2 * Ingresa el nombre del archivo a leer:
prueba1.txt * Cual es el nodo origen: e
-> Resultados <-
Camino: E->A costo: 5
Camino: E->D->C->B costo: 9
Camino: E->D->C costo: 7
Camino: E->D costo: 5
<- Que tenga un buen viaje! ->

El programa consta de dos clases cuyo código se incluyen en seguida.

// fecha 2007, compilador: j2sdk1.5.0_09  
import java.io.*;

class principal{

  public static void main(String args[]){

    int num=0;

    System.out.println("\n\tImplementacion del algoritmo de Dijkstra");
    System.out.print("Numero de nodos que tiene el grafo a resolver? ");

    do{
      try{
        InputStreamReader l1 = new InputStreamReader(System.in);
        BufferedReader l2 = new BufferedReader(l1);
        num=Integer.valueOf(l2.readLine()).intValue();
      }
      catch(IOException e){
        System.out.println("Error: "+e);
        System.out.println("Ingresa el numero de nodos que tiene el grafo a resolver: ");
      }
      catch(NumberFormatException e2){
        System.out.println("Error: "+e2);
        System.out.println("Ingresa el numero de nodos que tiene el grafo a resolver: ");
      }
      if(num<3 || num>26)
       System.out.print(" * El numero de nodos debe estar entre 3 y 26 ");

    }while(num<3 || num>26);
    dijkstra obj = new dijkstra(num);
  }
}

// fecha 2007, compilador: j2sdk1.5.0_09
import java.io.*;
import java.util.*;

public class dijkstra{

  int[][] matrizAdy;
  int nNodos;
  List conj_S = new ArrayList();
  List conjComp_S = new ArrayList();
  List caminos = new ArrayList();
  String tmp;
  InputStreamReader l1;
  BufferedReader l2;

  dijkstra(int numNodos){
    matrizAdy = new int[numNodos][numNodos];
    int aux=0;
    l1 = new InputStreamReader(System.in);
    l2 = new BufferedReader(l1);
    nNodos=numNodos;
    do{
      System.out.println(" * Ingresa el numero de opcion para cargar el grafo:\n1=Desde teclado\n2=Desde archivo");
      System.out.println("(El archivo debe ser de texto simple y estar formado por una matriz  de nxn donde:");
      System.out.println("n=numero de nodos y debe ser una matriz de adyacencia con la siguientes caracteristicas:");
      System.out.println("las aristas existentes se representaran por su costo, las no existentes y lazos por -1)");
      try{
        aux=Integer.valueOf(l2.readLine()).intValue();
      }
      catch(IOException e0){
        System.out.println("Error: "+e0);
        aux=0;
      }
      catch(NumberFormatException e1){
        System.out.println("Error: "+e1);
        aux=0;
      }
    }while(aux<1 || aux>2);
    if(aux==1)
      cargaDesdeTeclado();
    else
      cargaDesdeArchivo();
    do{
      try{
        System.out.print(" * Cual es el nodo origen: ");
        aux=((int)((l2.readLine()).toUpperCase()).charAt(0))-65;
      }
      catch(IOException e2){
        System.out.println("Error: "+e2);
        aux=-1;
      }
      catch(StringIndexOutOfBoundsException e3){
        System.out.println("Error: "+e3);
        aux=-1;
      }
    }while(aux<0 || aux>nNodos-1);
    matrizAdy[aux][aux]=0;
    resuelve(aux);
  }

  private void cargaDesdeTeclado(){
    boolean ocurrioError;
    System.out.println(" * Ahora ingresa los datos que se te soliciten: ");
    for(int cuenta=1;cuenta<=nNodos;cuenta++)
      for(int cnt=1;cnt<=nNodos;cnt++){
        if(cnt!=cuenta){
          System.out.println("Costo de la arista dirigida del nodo "+(char)(cuenta+64)+" al nodo "+(char)(cnt+64));
          System.out.print("(Ingresa 0 si la arista no existe) ");
          ocurrioError=false;
          try{
            matrizAdy[cuenta-1][cnt-1]=Integer.valueOf(l2.readLine()).intValue();
            ocurrioError=(matrizAdy[cuenta-1][cnt-1]<0?true:false);
            matrizAdy[cuenta-1][cnt-1]=(matrizAdy[cuenta-1][cnt-1]==0?-1:matrizAdy[cuenta-1][cnt-1]);
          }
          catch(IOException e0){
            System.out.println("Error: "+e0);
            ocurrioError=true;
          }
          catch(NumberFormatException e){
            System.out.println("Error: "+e);
            ocurrioError=true;
          }
          if(ocurrioError)
            cnt--;
        }
        else
          matrizAdy[cuenta-1][cuenta-1]=-1;
      }
  }

  private void cargaDesdeArchivo(){
    String nombAr;
    String a;
    StringTokenizer d;
    int f=0;
    int c=0;
    System.out.println(" * Ingresa el nombre del archivo a leer: ");
    try{
      nombAr=l2.readLine();
      FileReader ar = new FileReader(nombAr);
      BufferedReader b = new  BufferedReader(ar);
      while((a=b.readLine())!=null){
        d = new StringTokenizer(a);
        c=0;
        while(d.hasMoreTokens()){
          matrizAdy[f][c++]=Integer.valueOf(d.nextToken()).intValue();
        }
        f++;
      }
    }
    catch(FileNotFoundException e){
      System.out.print("Error: "+e);
      System.exit(0);
    }
    catch(IOException e1){
      System.out.print("Error: "+e1);
      System.exit(0);
    }
    catch(NumberFormatException e2){
      System.out.print("Error: "+e2);
      System.exit(0);
    }
  }

  private void resuelve(int origen){
    int nod;
    int minimo;
    int aux;
    int nodCambio=0;
    int intento;
    String tmp2;
    //Inicializando listas
    for(int i=0;i<nNodos;i++){
      if(i!=origen)
        conjComp_S.add(""+i);
      else
        conj_S.add(""+i);
      caminos.add("");
    }
    //Aplicando ciclo i de diksjtra
    for(int i=0;i<nNodos;i++){
      minimo=-1;
      for(int j=0;j<conjComp_S.size();j++){
        nod=Integer.valueOf((String)(conjComp_S.get(j))).intValue();
        aux=min(nod);
        if(minimo==-1 || (aux<minimo && aux!=-1)){
          minimo=aux;
          nodCambio=j;
        }
      }
      if(minimo!=-1){
        conj_S.add(""+(String)(conjComp_S.get(nodCambio)));
        conjComp_S.remove(nodCambio);
      }
    }
    //Imprimiendo resultados
    System.out.print("\n -> Resultados <-");
    for(int k=0;k<caminos.size();k++)
      if(k!=origen){
        tmp=(String)(caminos.get(k))+(char)(k+65);
        caminos.set(k,tmp);
      }
    for(int j=0;j<caminos.size();j++)
      if(j!=origen){
        intento=0;
        tmp=(String)(caminos.get(j));
          while(tmp.charAt(0)!=(char)(origen+65) && intento<10){
            aux=tmp.charAt(0)-65;
            tmp=((String)(caminos.get(aux)))+tmp.substring(1,tmp.length());
            if(++intento==10)
              tmp="*"+tmp;
          };
        imprimeCamino(tmp,j,origen);
      }
    System.out.println("\n <-  Que tenga un buen viaje! ->\n");
  }

  private int min(int dest){
    int min=-1;
    int nod=0;
    int nodOrig=-1;
    int aux;
    for(int i=0;i<conj_S.size();i++){
      nod=Integer.valueOf((String)(conj_S.get(i))).intValue();
      if(matrizAdy[nod][nod]!=-1 && matrizAdy[nod][dest]!=-1)
        aux=matrizAdy[nod][nod]+matrizAdy[nod][dest];
      else
        aux=-1;
      if((aux<min && aux!=-1)||min==-1){
        min=aux;
        nodOrig=nod;
      }
    }
    if(min!=-1){
      matrizAdy[dest][dest]=min;
      caminos.set(dest,""+(char)(nodOrig+65));
    }
    return min;
  }

  private void imprimeCamino(String cam, int nod, int o){
    System.out.print("\nCamino: ");
    if(cam.charAt(0)=='*')
      System.out.print("Te jodes: no hay camino de: "+(char)(o+65)+" a: "+cam.charAt(cam.length()-1)+"!!");
    else{
      for(int i=0;i<cam.length();i++)
        System.out.print(""+cam.charAt(i)+(i==cam.length()-1?"":"->"));
      System.out.print(" costo: "+matrizAdy[nod][nod]);
    }
  }
}

Comentarios

  1. Buenas compañero, muchas gracias por el código la verdad me ayudó bastante, solo una cosa que me manda error cuando quiero leer desde un archivo me pone esto

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
    at dijkstra.cargaDesdeArchivo
    at principal.main

    que me puede estar fallando compañero D:

    ResponderEliminar
    Respuestas
    1. Que tal amigo, significa que el archivo esta mal distribuido, revisa que en cada reglos haya 6 valores separados por un espacio.

      Eliminar
  2. HOLA si me podrias ayudar con el codigo fuente de la aplicaion grafica del algoritmo de prim

    ResponderEliminar
    Respuestas
    1. Hola, ya esta, ya lo tienes, va incluido en el jar ejecutable, abre el jar con winrar como si fuera un zip y ahi van los archivos java junto con los class.

      Eliminar
  3. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
    Respuestas
    1. Oops ya no alcance a responder, se trataba de cambiar los ceros por -1

      Eliminar
  4. si es q hay un archivo descargable no lo veo o es q ya se elimino?

    ResponderEliminar
    Respuestas
    1. En este caso no hay descargable, solo son las dos clases cuyo codigo esta publicado, lo puedes copiar directamente y compilar para obtener el class ejecutable.

      Eliminar
    2. si ya lo estoy estudiando muchas gracias

      Eliminar
    3. Este comentario ha sido eliminado por el autor.

      Eliminar
    4. Este comentario ha sido eliminado por el autor.

      Eliminar
    5. Cito
      "puedes explicarme esta linea de codigo po favor?
      System.out.print(" * Cual es el nodo origen: ");
      aux = ((int) ((l2.readLine()).toUpperCase()).charAt(0)) - 65;"

      La variable l2 es un BufferedReader que apunta al flujo de entrada (System.in), en otras palabras lee lo que se escriba en el teclado. Se espera que se escriba una letra del alfabeto, l2.readLine(), en realidad readline() lee una linea, lee lo que se escriba hasta que opriman enter, pero se espera que sea solo una letra, luego lo recibido ahi se convierte a mayusculas toUpperCase().

      Se supone que para ese momento tenemos una letra mayuscula y se le hace un cast y se convierte a entero, esto debe dar como resultado su valor en ascii, el ascii de A es 65 por eso se resta 65, asi si es una A el valor entero es 0, o sea nodo numero cero, o sea el primer nodo, y asi sucesivamente si es una B se convierte a 1, el segundo nodo, etc.

      Y finalmente el numero de nodo obtenido se guarda en aux. Eso hace la linea, por si escriben mas de un caracter (readLine()) se hace lo del .char(0) asi si por ejemplo escriben hola, solo se toma la primer letra en ese caso la h y se le hace el proceso de convertir a ascii y se le resta 65 y nos da el numero de nodo (en ese caso es el 7).

      Eliminar
  5. puedes subir un archivo plano, para ver como es la estructura al cargar el recorrido desde un archivo.

    ResponderEliminar
  6. para poder tener mas de 26 nodos??
    no me molestaria que mostrara el camino con numeros en vez de letras,
    por ejemplo Camino: 0->3->2->15->5->6 costo: 12
    hay alguna manera de modificarlo para que pueda tener mas nodos?

    ResponderEliminar
    Respuestas
    1. Claro que se puede modificar para eso esta disponible el codigo fuente.
      A mi tampoco me molestaria que el camino lo muestre con numeros o con letras dobles del tipo AA.
      De hecho si quieres trabajar con mas nodos sera necesario es una modificacion sencila y el codigo es libre, adelante amigo!

      Eliminar
    2. Hola que tal!
      Al querer cargar la matriz desde un archivo de texto, me aparece el siguiente error :
      " Error: java.io.FileNotFoundException: matriz.java (El sistema no puede encontrar el archivo especificado) "

      Eliminar
    3. Dannelson, tu archivo matriz.java no existe o no esta en la misma carpeta que que el class, y viendo que pones matriz.java, quizas no sea el archivo que se va a cargar? .java no estas confundiendo el codigo con los datos de entrada? checa eso.

      Eliminar
  7. Hola que tal podrías comentariar el código para poderlo entender mejor
    saludos!!

    ResponderEliminar
  8. Hola lo he entendido todo lo q no entiendo es pq marcas los nodos visitados, y si lo visitas otra vez con un costo menor?

    ResponderEliminar

Publicar un comentario

Entradas populares