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

starting edge,
ending edge, and
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?

John Bollinger · Accepted Answer · 2023-10-27 19:14:04Z

There may well be other problems with your code, but the issue you are asking about is surely caused by the comparator you have assigned to your PriorityQueue. Consider:

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

In that comparator, a.wei=b.wei is an assignment. You are modifying the wei field of one object being compared to be equal to the wei field of the other. The PairData objects you pull out of that queue will be the same ones you put in, but you are modifying them while they are inside.

And this is not merely a matter of getting mixed up between = (assignment) and == (equality comparison). Not only does the result of an == comparison have the wrong type, but an equality comparison is semantically the wrong computation to perform. A Comparator determines the relative order of pairs of objects, not just whether they are equal to each other. In particular, its compare() method must

Return[] a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Since your weights are modeled as ints, the Integer class provides a convenient way to write that:

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

dawooshifingerhold · Accepted Answer · 2023-10-27 17:50:29Z

0

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!

answered Oct 27, 2023 at 17:50

dawooshifingerhold

1001 gold badge1 silver badge7 bronze badges

Collectives™ on Stack Overflow

Priority Queue is not adding the correct data to the queue

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related