所以我正在尝试使用优先队列数据结构在java中实现Dijkstra算法。由于java中的可比较运算符无法比较两个变量,所以我需要“修改其Comparator
。 如何修改?
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
}
}
}
然后我遇到了这段代码:
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);
}
这段文本的大意是:“请帮忙解释一下代码中的q.add(((long) nprio << 32) + v);和cur >>> 32 != prio[curu]语句是如何工作的。”