在给定的dijkstra代码中，从Priority Queue中添加和删除元素有什么意义？

Question

我正在研究通过此链接给出的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());
}

Answer 1

首先，此代码很糟糕，因为priorityQueue.remove(v)需要O（n）时间，这使使用PriorityQueue https://docs.oracle.com/en/java/javase/11/docs/api/java.base/的整个目的无法实现java / util / PriorityQueue.html：

... remove（Object）的线性时间...

2）用一句话形容Dijkstra的算法：选择一个最小 的未访问顶点distance。要提取具有最小距离的顶点，您需要维护一个优先级队列，在该队列中，您可以按距离比较顶点（这是您要做的compareTo）。因此，提取的顶点将是距离最小的顶点。

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