Priority Queue is not adding the correct data to the queue

Question

I am trying to solve a problem using a priority queue, where I have a two dimensional array times where indexes in the second dimension representing

0. starting edge,
1. ending edge, and
2. the distance between two edges

Also given is the edge at which to start, as integer k.

I tried solving using Dijkstra's graph algorithm.

Since in the below code the starting node is 2, I am adding values [3,7] and [1,2] to the priority queue, but when polling the values I am getting [1,7] and [3,7]. It's working correctly for some other inputs, however.

Input:

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

Code:

  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));
    
        }
    }

What's wrong my code, such that I do not receive back the same values from the queue that I enqueued?

Answer 1

John is correct it seems like you need to be doing a return either Integer.compare(a.wei, b.wei) or returning a.wei < b.wei. This is because the way you have it currently set up makes it assign a.wei to b.wei in the anonymous comparator in the priority queue. Hope this helps!