Dijkstra算法中的未访问节点？

Question

在Dijkstra算法的优先队列实现中，我们删除顶部的节点，将其标记为已访问并更新与顶部相邻的所有顶点的距离值。

在这样做，我们需要检查是否靠近顶部的顶点已被访问还是我们不论是否已经访问过他们的还是不更新所有的顶点？

Answer 1

您是否有兴趣只知道节点的可达性或了解可达性以及最小距离？

• 对于只有可达性，一旦标记访问，不要更新它。
• 对于^†可达性和最小距离，如果距离小于（在节点+以达到从当前节点相邻节点的成本电流值），更新它。否则，保持原样。

---

^{†一种情况落在在这种情况下，当一个机器人试图找到从当前位置一些地方的最快路径。}

Answer 2

假设从优先级队列中删除的当前节点是cur那么我们需要检查cur节点是否可以找到任何边缘可以减少任何邻接节点的距离，那么我们需要更新距离。

注意，当节点是由这意味着我们已经找到该节点的最短距离从源头vertex.I认为你是混淆了一点，所以要在算法再次优先级队列中删除。

Answer 3

它取决于实施。

事实上，Dijkstra's Algorithm original pape r甚至没有提到堆 - 但它只处理连接到未访问节点的边（只检查未访问节点），一些实现（如CLRS中所代表的那些）更新所有节点连接到已处理的节点。

从Dijkstra的原始论文的相关报价：

最小长度从P路径是已知的（设置A）和其他（套 B，C）...考虑所有分支连接只是transfeired节点到 集合A，集合B或C中的节点

以上引用特别考虑只更新从未发现的节点。

Answer 4

这两种情况都没有问题（假设有负重循环，这是应用dijkstra的前提条件）。但是我们通常会删除高效代码的冗余，这就是为什么已经访问过的节点没有更新，因为它已经放松了。我们用这种方式检查

if(dist == initial distance) then only apply a step 

otherwise leave it...(pop and then go to next node in priority queue) 

希望这会有所帮助。现在，如果你忽略这一个，那么没有问题..没有复杂的变化，但冗长的检查relaxatation操作发生。