在给定的dijkstra代码中，从Priority Queue中添加和删除元素有什么意义？ [英] What is the point of adding and removing the element from Priority Queue in the given dijkstra code?

问题描述

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

I was studying Dijkstra algorithm code given at this link -> https://java2blog.com/dijkstra-java/

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

Can someone explain the following 2 parts of the code?

1）为什么当计算距离较小时，是否要从优先级队列中添加和删除元素？

1) Why are we adding and removing the element from Priority queue when calculate distance is less?

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

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

2) What are we doing in compareTo method and why?

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

推荐答案

首先，这段代码这很不好，因为 priorityQueue.remove（v）需要O（n）时间，这违背了使用 PriorityQueue https：// docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html ：

To begin with, this code is bad, since priorityQueue.remove(v) requires O(n) time, which defeats the whole purpose of using PriorityQueue https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html:

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

... linear time for the remove(Object) ...

2）Dijkstra算法在一个短语中：选择一个最小 距离的未访问顶点。要提取具有最小距离的顶点，您需要维护一个优先级队列，在其中按距离比较顶点（这是您的 compareTo 所做的事情）。因此，提取的顶点将是距离最小的顶点。

2) Dijkstra's algorithm in one phrase: select a non-visited vertex with a smallest distance. To extract the vertex with a smallest distance, you maintain a priority queue, where you compare vertices by distance (this is what your compareTo does). So the vertex which is extracted will be the vertex with the smallest distance.

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

1) Data structures have some assumptions. If these assumptions are violated, data structures may work incorrectly. In case of PriorityQueue the assumption is "for any elements in the queue the result of comparison doesn't change". And, since you compare using distance, if you change the distance, then the result of comparison may also change, leaving your PriorityQueue in potentially invalid state. Therefore, you first remove the element, and only after that change the distance.

这篇关于在给定的dijkstra代码中，从Priority Queue中添加和删除元素有什么意义？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！