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]);
    }
  }
}