我看到了dijkstra算法的实现,我不太了解这段代码的某些部分:
public static void computePaths(Vertex source) {
source.minDistance = 0;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies) {
Vertex v = e.target;
double distanceThroughU = u.minDistance + e.getweight();
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v); //How can I remove if I didn't add it first, and why do I need to remove?
v.minDistance = distanceThroughU;
v.previous = u;
vertexQueue.add(v); //Why is it add again?
}
}
}
}
我读到了关于dijkstra算法的知识,所以我知道了一般的逻辑,但是当我看到这个实现时,有一些我不明白为什么要完成它们。有人可以试着解释一下吗?特别是我有评论的地方!
更新节点v的信息
您希望更新存储在优先级队列中的节点v的信息,因为您找到了更短的路径。
如果节点存在于优先级队列中,则Remove()函数将删除该节点。
之后,您更新信息,然后使用更新的信息再次添加。