Исключение в потоке «main» java .lang.ClassCastException: javafx.util.Pair не может быть преобразован в java .lang.Comparable

Question

Кроме того, этот вопрос задавали много раз, я не могу понять это в соответствии с моим решением. Я пишу алгоритм Дейкстры для взвешенного графа. Я использовал ArrayList >> для хранения моих весов и ребер. При реализации функции Дейкстры я использовал MinHeap, который является PriorityQueue в java типа Pair . Во время добавления пар в кучу я получаю эту ошибку.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import javafx.util.Pair; 

public class Solution{

    public static void dijkstra(ArrayList<ArrayList<Pair<Integer, Integer>>> graph, int V, int E, int S) {
        int dist[] = new int[V+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;

        PriorityQueue< Pair<Integer, Integer> > heap = new PriorityQueue<>();

        heap.add(new Pair<Integer, Integer>(0, S) );

        while(heap.size() != 0) {
            Pair<Integer, Integer> curr = heap.poll();
            int w = curr.getKey(), x = curr.getValue();
            System.out.println(x);
            if(w <= dist[x]) {
                for(Pair<Integer, Integer> temp : graph.get(x)){
                    int x2 = temp.getKey(), w2 = temp.getValue();
                    if(w+w2 < dist[x2]){
                        dist[x2] = w + w2;

      //Facing the error in below line

                        heap.add(new Pair<Integer, Integer>(w+w2, x2));
                    }
                }
            }
        }
        for(int i = 1; i <= V; i++) {
            if(i == S) continue;
            if(dist[i] == Integer.MAX_VALUE)
                System.out.print("-1 ");
            else
                System.out.print(dist[i]+" ");
        }
    }
//Adding edge to a graph
    public static void addEdge( ArrayList<ArrayList<Pair<Integer, Integer>>> graph, int u, int v, int w){
        graph.get(u).add(new Pair<Integer, Integer>(v, w));
        graph.get(v).add(new Pair<Integer, Integer>(u, w));
    }
//Main Function
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while(t-- != 0) {
            int n = in.nextInt();
            int m = in.nextInt();
            ArrayList<ArrayList<Pair<Integer, Integer>>> graph = new ArrayList<>();
            for(int i = 0; i <= n; i++) {
                graph.add(new ArrayList<Pair<Integer, Integer>>());
            }

            for(int i = 0; i < m; i++) {
                addEdge(graph, in.nextInt(), in.nextInt(), in.nextInt());
            }
            int s = in.nextInt();
            dijkstra(graph, n, m, s);
            System.out.println();
        }
    }

}

Я также добавляю дубликаты в кучу, так как это не влияет на мой алгоритм.

Answer 1

Поскольку PriorityQueue поддерживает отсортированный порядок объектов, которые он хранит, И для этого ему требуется некоторый журнал сравнения c между объектами.

В вашем случае это Pair, поэтому ошибка просит вас сделать ваш класс Pair реализует интерфейс Comparable или предоставляет очередь приоритетов компаратору для сортировки парных объектов.

Посмотрите на это https://www.callicoder.com/java-priority-queue/

В основном вам нужно предоставить собственный компаратор.