CODEWITHSUNDEEP
javaalgorithm
user4996457
user4996457

Reputation: 161

Dijkstra's algorithm using the priority queue

So I am trying to implement Dijkstra's algorithm using the priority queue data structure in java. Since comparable operator in java cannot compare two variables, so i need to "modify its Comparator. How do I modify it ?

 while(!Q.isEmpty()){
         int index = Q.peek().edge;
         long d = Q.peek().dis;
         Q.remove();

         if(d!=D[index]) continue; // HERE I AM CHECKING IF IT ALREADY PROCEEDED OR NOT

         for(int i=0;i<maps[index].size();i++){
               int e = maps[index].get(i).edge;
                d =  maps[index].get(i).dis;
                if(D[e]>D[index]+d){
                    D[e]= D[index]+d;
                    Q.add(new Node(e,D[e])); // NEED TO MODIFY
                }
         }
     }



Then i came across this code:

 while (!q.isEmpty()) {
      long cur = q.remove();
      int curu = (int) cur;
      if (cur >>> 32 != prio[curu])
        continue;
      for (Edge e : edges[curu]) {
        int v = e.t;
        int nprio = prio[curu] + e.cost;
        if (prio[v] > nprio) {
          prio[v] = nprio;
          pred[v] = curu;
          q.add(((long) nprio << 32) + v);
        }

How q.add(((long) nprio << 32) + v); and cur >>> 32 != prio[curu] statements works. Please HElp.

Upvotes: 3

Views: 642

Answers (1)

kutschkem
kutschkem

Reputation: 8163

Java's Priorityqueue sorts according to the natural ordering if no comparator is given.

You either need to:

  1. implement compareTo in your Node class
  2. create a Comparator that compares your nodes according to priority (priority = distance from start for Dijkstra)

The second code you showed uses the upper 32 bits of a long to store the priority, thereby making the natural order reflect the distance from start.

Basically, the code is 100% the same as yours, with the difference being the data structure. You use a class, the second code uses a long to embed two integers (node id and distance/priority).

Upvotes: 1

Related Questions