0

我正在研究此链接中给出的 Dijkstra 算法代码-> https://java2blog.com/dijkstra-java/

有人可以解释代码的以下两部分吗？

1）当计算距离较小时，为什么我们在优先队列中添加和删除元素？

if( newDistance < v.getDistance() ) {
    priorityQueue.remove(v);
    v.setDistance(newDistance);
    v.setPredecessor(actualVertex);
    priorityQueue.add(v);
}

2) 我们在 compareTo 方法中做了什么，为什么？

@Override
public int compareTo(Vertex otherVertex) {
    return Double.compare(this.distance, otherVertex.getDistance());
}
4

2 回答 2

5

首先，这段代码很糟糕，因为需要 O(n) 时间，这违背了使用https://docs.oracle.com/en/java/javase/11/docs/api/java.base/priorityQueue.remove(v)的全部目的PriorityQueue java/util/PriorityQueue.html：

... remove(Object) 的线性时间 ...

2) Dijkstra 算法一句话：选择一个最小 distance的未访问顶点。要提取距离最小的顶点，您需要维护一个优先级队列，在其中按距离比较顶点（这就是您compareTo所做的）。所以提取的顶点将是距离最小的顶点。

1）数据结构有一些假设。如果违反这些假设，数据结构可能无法正常工作。如果PriorityQueue假设是“对于队列中的任何元素，比较结果不会改变”。而且，由于您使用 进行比较distance，如果您更改distance，那么比较的结果也可能会发生变化，从而使您PriorityQueue处于潜在的无效状态。因此，您首先删除元素，然后才更改距离。

于 2019-09-08T18:17:46.000 回答
2

1) PriorityQueue 仅在插入条目时评估优先级。仅仅改变priority onv不会引起这个评估，所以不会有效果。

2) 的基本合同compareTo是当两个实例或被认为相等时它返回 0。1 如果这被认为是“更大” -1 如果这被认为是“更小”。为一个值Double.compare(..)创建这个语义。Double

于 2019-09-08T18:16:34.417 回答