dijkstra on multiple graphs Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract

Question

i am trying to implement dijkstra on hackerrank it give correct ans for first graph in every testcase but exception if testcase have more than 1 graph in it `import java.io.*;

import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
public static class Node implements Comparable<Node>{
    int dst=Integer.MAX_VALUE;
    boolean visit=false;
    int index;
    Node(){};
    Node(int index){
        this.index=index;
    };

    public int compareTo(Node n1){
        try{
        return dst<n1.dst?-1:1;
       }catch(Exception e){return 1;}
    }
}
    public static class Edge{
        int index;
        int dst=0;
        Edge(){}
        Edge(int inedx){
            this.index=index;
        }


    }
       public static Node[] dij(ArrayList<Node> nod,ArrayList<LinkedList<Edge>> aee,Node[] nrr){

        while(!nod.isEmpty()){
        Collections.sort(nod);
        Node ne=nod.remove(0);
        LinkedList<Edge> queue=aee.get(ne.index);
        while(!queue.isEmpty()){
            Edge temp=queue.remove(0);
            if((nrr[temp.index].dst>(nrr[ne.index].dst+temp.dst)&&(nrr[ne.index].dst!=Integer.MAX_VALUE))){
                nrr[temp.index].dst=nrr[ne.index].dst+temp.dst;
            }
        }

        }
        return nrr;
    }
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
   Scanner in=new Scanner(System.in);
        int t=in.nextInt();
        while(t-->0){
            int n=in.nextInt();
            Node nrr[]=new Node[n];
            ArrayList<Node> nod=new ArrayList<>();
            for(int i=0;i<n;i++){
                Node ne=new Node(i);
                nrr[i]=ne;
                nod.add(ne);
            }
            int m=in.nextInt();
            ArrayList<LinkedList<Edge>> aee=new ArrayList<LinkedList<Edge>>(n);
            for(int i=0;i<n;i++)
                aee.add(new LinkedList<Edge>());
            for(int i=0;i<m;i++){
                int start=in.nextInt()-1;
                int end=in.nextInt()-1;
                int dst=in.nextInt();
                Edge e1=new Edge(end);
                e1.dst=dst;
                e1.index=end;
                //System.out.println(start+" "+end+" dd "+dst+" "+e1.index);
                aee.get(start).add(e1);
                Edge e2=new Edge(start);
                e2.index=start;
                e2.dst=dst;
               // System.out.println("dd");
                aee.get(end).add(e2);
                nrr[start].visit=true;
                nrr[end].visit=true;
            }
            int k=in.nextInt()-1;
            nrr[k].dst=0;
            Node[] nn=dij(nod,aee,nrr);
            int temp=Integer.MAX_VALUE+0;
      //  System.out.println(temp+" tem");
        for(int i=0;i<n;i++){
            if(i!=k)
                System.out.print(nn[i].dst+" ");
        }
            System.out.println();
        }


    }
}

this is my code with queue and comparable is use to sort my queue this is input

2
20 54
1 7 45
2 14 15
3 7 29
4 1 48
5 1 66
6 7 17
7 14 15
8 14 43
9 1 27
10 1 33
11 14 64
12 14 27
13 7 66
14 7 54
15 14 56
16 7 21
17 1 20
18 1 34
19 7 52
20 14 14
9 14 9
15 1 39
12 1 24
9 1 16
1 2 33
18 1 46
9 1 28
15 14 3
12 1 27
1 2 5
15 1 34
1 2 28
9 7 16
3 7 23
9 7 21
9 14 19
3 1 20
3 1 5
12 14 19
3 14 2
12 1 46
3 14 5
9 14 44
6 14 26
9 14 16
9 14 34
6 7 42
3 14 27
1 7 9
1 7 41
15 14 19
12 7 13
3 7 10
1 7 2
17
78 1231
1 49 8
2 75 36
3 47 38
4 46 11
5 50 61
6 47 45
7 18 38
8 31 39
9 78 18
10 15 11
11 5 1
12 23 26
13 48 58
14 33 60
15 22 3
16 27 27
17 32 17
18 65 40
19 23 55
20 12 41
21 39 37
22 14 18
23 20 25
24 4 19
25 3 12
26 25 15
27 13 6
28 73 10
29 62 60
30 44 18
31 18 44
32 78 3
33 39 29
34 26 42
35 22 24
36 18 36
37 16 41
38 46 54
39 51 2
40 49 16
41 38 22
42 6 44
43 24 49
44 55 36
45 6 63
46 45 10
47 48 41
48 58 21
49 50 24
50 27 17
51 59 38
52 68 33
53 4 4

Your Output
20 25 25 68 86 39 22 70 36 53 91 35 88 27 30 43 54 74 41 
Error
Exception in thread "main" java.util.NoSuchElementException
    at java.util.Scanner.throwFor(Scanner.java:907)
    at java.util.Scanner.next(Scanner.java:1530)
    at java.util.Scanner.nextInt(Scanner.java:2160)
    at java.util.Scanner.nextInt(Scanner.java:2119)
    at Solution.main(Solution.java:67)

I am not able to improve this.

Did you read the Javadoc on `Comparable.compareTo`? Specifically the part about how it has to return zero if the inputs are equal? — Louis Wasserman, Jul 13 '17 at 15:13
Yes, I noticed you're returning 1 and -1. That's (at least part of) what's wrong. — Louis Wasserman, Jul 13 '17 at 17:50
i am returning 1 and -1 by my understanding it will compare value with all and swap when it return -1 and not when it is 1(sort ascending or descending ). so when they are equal it return 1 and swap will not happen , am i right? — Rajan Lagah, Jul 13 '17 at 18:05
Read the Comparable Javadoc and follow it. You must return zero when they are equal. You must return a negative number when the first is less than the second. You must return a positive number when the first is greater than the second. If you don't follow those rules, you will get exceptions like this. — Louis Wasserman, Jul 13 '17 at 18:07
sir, inside while loop i print something(System.out.println("on");) it take first graphs input and give its right ans but when it run for second graph then it throw exception; (becoz it print on 2 time before first and before second and then throw the exception) — Rajan Lagah, Jul 13 '17 at 18:11
Yes, and? It doesn't always catch the issue with a comparator, but it always needs to be addressed. This is perfectly normal and doesn't change that you need to fix your compareTo implementation. — Louis Wasserman, Jul 13 '17 at 18:13
okay sir, @talex also said me to return 0. but after returning 0 the conditions are same . i also search it on google .they said when the thing u are comparing is null then it will throw exception .but dst is always having some value . i also try comparator but he is able to handle all graphs correctly except the last one . plz sir find out mistake , implementing dijkestra is awesome thing , and i also invested a lot of time . so the problem must be something great from my level. — Rajan Lagah, Jul 13 '17 at 18:22

score 0 · Answer 1 · answered Jul 13 '17 at 15:14

Your compareTo violate contract. In case of two nodes have same dst you get n1.compareTo(n2) == 1 and n2.compareTo(n1) == 1.

Correct version should look like this.

 public int compareTo(Node n1){
    return dst<n1.dst?-1:(dst>n1.dst?1:0);
 }

PS: I don't know why you catch exceptions there. n1 can't be null.

dijkstra on multiple graphs Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract

1 Answers1