java - Dijkstra算法中使用的优先级队列的比较器类实现？

Question

我正在尝试实现 CLRS - 算法简介书中的 Dijsktra 算法，但是，我在使用 Comparator 实现优先级队列时遇到了麻烦。界面。如您所见，这是我的 Vertex 类；

public class Vertex {

    public boolean explored;
    public int vertexID;
    public LinkedList<Vertex> adjacencyList;
    public LinkedList<Edge> edgeSet;
    public int shortestDistance;
    public Vertex predecessor;

    public Vertex(int vertexID){

        this.vertexID = vertexID;
        this.explored = false;
        this.adjacencyList = new LinkedList<>();
        this.edgeSet = new LinkedList<>();
        this.shortestDistance = Integer.MAX_VALUE;
        this.predecessor = null;
    }
}

所以最初shortestDistance属性声明为Integer.MAX_VALUE 。此外，您可以看到从 Comparator 实现的类，用于优先级队列。

public class WeightComparator implements Comparator<Vertex> {

    @Override
    public int compare(Vertex o1, Vertex o2) {

        return Math.min(o1.shortestDistance, o2.shortestDistance);
    }
}

由于我的一些测试，我确信整个实现没有任何逻辑错误，但是，在一些测试中它失败了。我使用此语句创建对我的队列的引用

PriorityQueue<Vertex> queue = new PriorityQueue<>(N, weightComparator);

其中 N 是队列的大小。因此，如果我对其工作方式的理解有误，请纠正我。当你 poll从中删除一个项目，它将删除优先级最低的项目？希望大家能清楚地理解我的问题，如果有人能对此提供帮助，我将不胜感激。所以还是谢谢了

Answer 1

Math.min 为您提供两个值中较小的一个。将其作为比较值返回是错误的。

compare 返回值 <0 表示第一个值小于第二个值，但如果返回 Math.Min(5, 3)，您将得到3，>0，这意味着比较器会告诉它 3 > 5。这是错误的。

您正在寻找的是:

public int compare(Vertex o1, Vertex o2) {
    return Integer.compare(o1.shortestDistance, o2.shortestDistance);
}