0

我正在尝试从 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从中获取项目时，它将删除优先级最低的项目？希望很清楚地了解我的问题，如果有人能对此提供帮助，我将不胜感激。所以还是谢谢

4

2 回答 2

6

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

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

您正在寻找的是：

public int compare(Vertex o1, Vertex o2) {
    return Integer.compare(o1.shortestDistance, o2.shortestDistance);
}
于 2013-08-06T23:40:22.637 回答
2

除非shortestDistance可以是负数，否则您的比较器永远不会返回负数。因此，这不是一个正确的实现。

从概念上讲，原语的比较器应该返回一个减法：

return o1.shortestDistance-o2.shortestDistance;

或者如果你想下降，反之亦然。但是你需要提防溢出问题。

于 2013-08-06T23:39:10.553 回答