Dijkstra算法使用优先队列

Question

所以我正在尝试使用优先队列数据结构在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]语句是如何工作的。”

- user4996457

---

有符号左移位运算符“<<”将位模式向左移动，有符号右移位运算符“>>”将位模式向右移动。位模式由左操作数给出，要移动的位置数由右操作数给出。无符号右移位运算符“>>>”将零移入最左侧位置，而“>>”后的最左侧位置取决于符号扩展。 - Balkrishna Rawool

如何在上述算法中使用它，即在优先队列中进行比较，可以获得它的有用性。 - user4996457

Answer 1

如果没有提供比较器，Java的PriorityQueue会根据自然排序进行排序。

你需要做以下两件事情之一：

1. 在你的Node类中实现compareTo方法
2. 创建一个比较器，按照优先级（Dijkstra算法中与起点的距离）比较节点

你展示的第二段代码使用长整型的前32位来存储优先级，因此使得自然排序反映了距离起点的距离。

基本上，这段代码与您的代码完全相同，不同之处在于数据结构。您使用一个类，而第二段代码使用一个长整型来嵌入两个整数（节点ID和距离/优先级）。

- kutschkem

---

请解释一下第二段代码中的hack用法，即将一个长整型的32位用于存储优先级。 - user4996457

@user4996457 由于它们是高位，它们决定了顺序。 - kutschkem