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