Dijkstra's Algorithm explanation java

Question

Hi,

I have found an implementation for dijkstras algorithm on the internet and was wondering if someone could help me understand how the code works.

Many thanks

 private int nr_points=0;
 private int[][]Cost;
 private int []mask;

 private void dijkstraTSP()
   {
    if(nr_points==0)return;
    //algorithm=new String("Dijkstra");

    nod1=new Vector(); 
    nod2=new Vector();
    weight=new Vector();
    mask=new int[nr_points];
    //initialise mask with zeros (mask[x]=1 means the vertex is marked as used)
    for(int i=0;i<nr_points;i++)mask[i]=0;
    //Dijkstra:
    int []dd=new int[nr_points];
    int []pre=new int[nr_points];
    int []path=new int[nr_points+1];
    int init_vert=0,pos_in_path=0,new_vert=0;

    //initialise the vectors
    for(int i=0;i<nr_points;i++)
    {
       dd[i]=Cost[init_vert][i];
       pre[i]=init_vert;
       path[i]=-1;
    }
    pre[init_vert]=0;
    path[0]=init_vert;
    pos_in_path++;
    mask[init_vert]=1;

    for(int k=0;k<nr_points-1;k++)
    {
        //find min. cost in dd
        for(int j=0;j<nr_points;j++)
           if(dd[j]!=0 && mask[j]==0){new_vert=j; break;}

        for(int j=0;j<nr_points;j++)
           if(dd[j]<dd[new_vert] && mask[j]==0 && dd[j]!=0)new_vert=j;

        mask[new_vert]=1;
        path[pos_in_path]=new_vert;
        pos_in_path++;
        for(int j=0;j<nr_points;j++)
        {
           if(mask[j]==0)
           {
              if(dd[j]>dd[new_vert]+Cost[new_vert][j])
              {
                 dd[j]=dd[new_vert]+Cost[new_vert][j];
              }
           }
        }
    }
    //Close the cycle
    path[nr_points]=init_vert;

    //Save the solution in 3 vectors (for graphical purposes)
    for(int i=0;i<nr_points;i++)
    {
       nod1.addElement(path[i]);
       nod2.addElement(path[i+1]);
       weight.addElement(Cost[path[i]][path[i+1]]);
    }            
}

Answer 1

I think you need something like that: http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29

Answer 2

Before go through the algorithm. See the links:

link 1

link2

link3

Then you will clear about your algorithm.

Answer 3

Here is a better solution based on pseudo-code of the algorithm in a book Introductions to Algorithms.

The book also has a good explanation of the algorithm and should be found in libraries everywhere. It also describes many other graph algorithms if you are interested.

public static void Dijkstra(Graph g, int s) {
    InitializeSingleSource(g, s);
    DistanceComparator dc = new DistanceComparator();
    PriorityQueue<Graph.Vertex> q = new PriorityQueue<Graph.Vertex>(g.size(),
                                                                    dc);
    for (int i = 0; i < g.size(); i++) {
        q.add(g.getVertex(i));
    }
    while (!q.isEmpty()) {
        Graph.Vertex u = q.poll();
        for (int i = 0; i < g.size(); i++) {
            if (g.hasEdge(u.getIndex(), i)) Relax(g, u.getIndex(), i);
        }
    }
}

private static class DistanceComparator implements Comparator<Graph.Vertex> {
    public int compare(Graph.Vertex a, Graph.Vertex b) {
        if (a.getDistance() > b.getDistance()) {
            return 1;
        } else if (a.getDistance() == b.getPredecessor()) {
            return 0;
        } else {
            return -1;
        }
    }
}

private static void Relax(Graph g, int u, int v) {
    if (g.getDistance(u) == Graph.INFINITY) return;
    if (g.getDistance(v) > g.getDistance(u) + g.getWeight(u, v)) {
        g.setDistance(v, g.getDistance(u) + g.getWeight(u, v));
        g.setPredecessor(v, u);
    }
}

private static void InitializeSingleSource(Graph g, int s) {
    for (int i = 0; i < g.size(); i++) {
        g.setDistance(i, Graph.INFINITY);
        g.setPredecessor(i, -1);
    }
    g.getVertex(s).setDistance(0);
}