java - Dijkstra's algorithm using the priority queue -

so trying implement dijkstra's algorithm using priority queue data structure in java. since comparable operator in java cannot compare 2 variables, need "modify comparator. how modify ?

 while(!q.isempty()){          int index = q.peek().edge;          long d = q.peek().dis;          q.remove();           if(d!=d[index]) continue; // here checking if 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 modify                 }          }      } 

then came across code:

 while (!q.isempty()) {       long cur = q.remove();       int curu = (int) cur;       if (cur >>> 32 != prio[curu])         continue;       (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); , cur >>> 32 != prio[curu] statements works. please help.

java's priorityqueue sorts according natural ordering if no comparator given.

you either need to:

1. implement compareto in node class
2. create comparator compares nodes according priority (priority = distance start dijkstra)

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

basically, code 100% same yours, difference being data structure. use class, second code uses long embed 2 integers (node id , distance/priority).