Dijkstra in java

[- En español -]

The Dijkstra algorithm has to do with graphs algorithms. This algorithm are made to find the shortest path from a given point (node) to another inside a weighted graph.

A weighted graph is a graph which its nodes are conected by edges with a given weight, called cost, every edge is one way directed. As the shown on the following figure:

In the graph we can see, to go from A node to C node there is an edge, a way, with a cost of 3 units, but to go from A to E there's no a directly way but it has to go trough another nodes, the question is: Which option has the lower cost? Going by the B, D or C node?

To solve the described question programmatically is by programing the Dijkstra algorithm.

The way I used its based on represent the graph by an adjacency array, where every weight is placed in a NxN array where N is the total nodes and where every cell, row with column intersect, has the weight of the edge from column node to row node. The graph from the previous figure becomes in an adjacency array this way:

	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

The red values means there is not an edge or its a cycle (a way starting from a node and ending on same node).

I made the program on command line mode, it can read edge values one by one or the whole array from a flat text file, the previous array in a text file must be contain only the values, separated by a blank, no heads for column or rows, this way:

-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

The run and output for the program (using the figure graph) gives this:

..[command line]..>java principal

Dijkstra's algorithm
How many nodes has the graph to solve? 5
* Type the option number to load the graph:
1=From standar input (keyboard)
2=From file
(The file must be flat text type and be formed by an nxn array where:
n=nodes number, the adjancecy array must have the following characteristics:
the edges are represented by its value, the unpresent edges and cicles by -1)
2
* Type the file's name to use:
array.txt
* Which is the origin node: e

-> Results <-
Path: E->A weight: 5
Path: E->D->C->B weight: 9
Path: E->D->C weight: 7
Path: E->D weight: 5
<- Have a nice travel! ->

The program use two class, the source is following.

// year 2007, compiler: j2sdk1.5.0_09
import java.io.*;

class principal{

  public static void main(String args[]){
    int num=0;
    System.out.println("\n\tDijkstra's algorithm");
    System.out.print("How many nodes has the graph to solve? ");
    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("Type the number of nodes the graph to solve has: ");
      }
      catch(NumberFormatException e2){
        System.out.println("Error: "+e2);
        System.out.println("Type the number of nodes the graph to solve has: ");
      }
      if(num<3 || num>26)
       System.out.print(" * The number must be between 3 and 26 ");
    }while(num<3 || num>26);
    dijkstra obj = new dijkstra(num);
  }
}

// year 2007, compiler: 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(" * Type the option number to load the graph:\n1=From standar input (keyboard)\n2=From file");
      System.out.println("(The file must be flat text type and be formed by an nxn array where:");
      System.out.println("n=nodes number, the adjancecy array must have the following characteristics:");
      System.out.println("the edges are represented by its value, the unpresent edges and cicles by -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(" * Which is the origin node: ");
        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(" * Type the required data: ");
    for(int cuenta=1;cuenta<=nNodos;cuenta++)
      for(int cnt=1;cnt<=nNodos;cnt++){
        if(cnt!=cuenta){
          System.out.println("Edge weight from node "+(char)(cuenta+64)+" to node "+(char)(cnt+64));
          System.out.print("(Type 0 if the edge does not exists) ");
          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(" * Type the file's name to use: ");
    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;
    //Starting lists
    for(int i=0;i<nNodos;i++){
      if(i!=origen)
        conjComp_S.add(""+i);
      else
        conj_S.add(""+i);
      caminos.add("");
    }
    // Appling diksjtra process
    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);
      }
    }
    //Printing results
    System.out.print("\n -> Results <-");
    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 <-  Have a nice travel! ->\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("\nPath: ");
    if(cam.charAt(0)=='*')
      System.out.print("Sorry: there's no a path from: "+(char)(o+65)+" to: "+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(" weight: "+matrizAdy[nod][nod]);
    }
  }
}