java - 使用优先级队列的 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]语句有效。请帮忙。

Answer 1

如果没有给出比较器，Java 的 Priorityqueue 将根据自然顺序进行排序。

您要么需要:

1. 在您的 Node 类中实现 compareTo
2. 创建一个比较器，根据优先级比较您的节点(对于 Dijkstra，优先级 = 距起点的距离)

您显示的第二个代码使用 long 的高 32 位来存储优先级，从而使自然顺序反射(reflect)距开始的距离。

基本上，代码与您的代码 100% 相同，区别在于数据结构。你使用一个类，第二个代码使用一个 long 来嵌入两个整数(节点 id 和距离/优先级)。