Dijkstra's algorithm using a priority queue
So I am trying to implement Dijkstra's algorithm using the priority queue data structure in java. Since the comparable operator in java cannot compare two variables, so I need to "change it Comparator
. How can I change 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 instructions work q.add(((long) nprio << 32) + v);
and cur >>> 32 != prio[curu]
. Please HElp.
source to share
Java Priorityqueue sorts according to natural ordering if no comparator is specified.
You either need:
- implement compareTo in Node class
- create a comparator that compares your nodes according to priority (priority = distance from origin for Dijkstra)
The second code you provided uses the upper 32 bits long to preserve priority, thus making the natural order a reflection of the distance from the origin.
Basically, the code is 100% the same as yours, with the difference that the data structure. You are using a class, the second code is using long nesting of two integers (node id and distance / priority).
source to share