优先级队列未将正确的数据添加到队列中

Question

我正在尝试使用优先级队列解决问题，其中我有一个二维数组

times

，其中第二维中的索引代表

0. 起始边缘，
1. 结束边缘，以及
2. 两条边之间的距离

还给出了开始的边缘，作为整数

k

。

我尝试使用 Dijkstra 的图算法来求解。

由于在下面的代码中起始节点是 2，我将值 [3,7] 和 [1,2] 添加到优先级队列，但是在轮询值时我得到 [1,7] 和 [3, 7]. 但是，对于其他一些输入，它可以正常工作。

输入：

 int times[][] = {{1,2,1},{2,3,7},{1,3,4},{2,1,2}};
 int n = 3, k = 2;

代码：

  import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.PriorityQueue;
    
    class PairData {
        int node;
        int wei;
    
        public PairData(int node, int wei) {
            this.node = node;
            this.wei = wei;
        }
    }
    public class NetworkDelayTime {
    
        public int networkDelayTime(int[][] times, int n, int k) {
    
            ArrayList<ArrayList<PairData>> adj= new ArrayList<>();
    
            for(int i=0;i<n+1;i++){
                adj.add(new ArrayList<PairData>());
            }
    
            for (int i=0;i<times.length;i++){
    
               adj.get(times[i][0]).add(new PairData(times[i][1],times[i][2]));
    
            }
    
            PriorityQueue<PairData>  pq= new PriorityQueue<>((a,b)-> {
                System.out.println(a.node+" "+a.wei);
                System.out.println(b.node+" "+b.wei);
               return a.wei=b.wei;
            });
    
            pq.add(new PairData(k,0));
    
            int[] ans = new int[n+1];
            Arrays.fill(ans,Integer.MAX_VALUE);
            ans[k]=0;
    
    
            while (!pq.isEmpty()){
                PairData data=pq.poll();
                int v=data.node;
                int dis=data.wei;
                System.out.println("the poll data "+v);
                System.out.println("the poll data weight "+dis);
    
               for(PairData pa:adj.get(v)){
                   int curDis=pa.wei+dis;
                   if(curDis<ans[pa.node]){
                       ans[pa.node]=curDis;
                       System.out.println("The current node adding to "+curDis);
                       PairData pairData=new PairData(pa.node,curDis);
                       pq.add(pairData);
                   }
    
               }
    
            }
    
           int min=Integer.MAX_VALUE;
            System.out.println(Arrays.toString(ans));
            for(int i=1;i<=n;i++){
                if(ans[i]==Integer.MAX_VALUE)
                    return -1;
                min=Math.max(ans[i],min);
            }
    
    
    
            return min;
    
        }
    
        public static void main(String[] args) {
    
                int times[][] = {{1,2,1},{2,3,7},{1,3,4},{2,1,2}};
                int n = 3, k = 2;
    
                NetworkDelayTime delayTime = new NetworkDelayTime();
    
                System.out.println(delayTime.networkDelayTime(times, n, k));
    
        }
    }

我的代码出了什么问题，以至于我没有从排队的队列中收到相同的值？

Answer 1

您的代码很可能存在其他问题，但您所询问的问题肯定是由您分配给

PriorityQueue

的比较器引起的。考虑：

            PriorityQueue<PairData>  pq= new PriorityQueue<>((a,b)-> {
                System.out.println(a.node+" "+a.wei);
                System.out.println(b.node+" "+b.wei);
               return a.wei=b.wei;
            });

在该比较器中，

a.wei=b.wei

是一个赋值。您正在修改一个正在比较的对象的

wei

字段，使其等于另一个对象的

wei

字段。您从队列中取出的

PairData

对象将与您放入的对象相同，但您是在它们位于队列中时对其进行修改。

这不仅仅是混淆

=

（赋值）和

==

（相等比较）的问题。不仅

==

比较的结果类型错误，而且相等比较在语义上执行的计算也是错误的。 A

Comparator

决定了对象对的相对顺序，而不仅仅是它们是否彼此相等。特别是它的

compare()

方法必须

当第一个参数小于、等于或大于第二个参数时，返回[]负整数、零或正整数。

由于您的权重被建模为

int

，因此

Integer

类提供了一种方便的书写方式：

            PriorityQueue<PairData>  pq= new PriorityQueue<>((a,b)-> {
                System.out.println(a.node+" "+a.wei);
                System.out.println(b.node+" "+b.wei);
                return Integer.compare(a.wei, b.wei);
            });