当合并权重小于节点权重时，为什么要放入队列？

Question

正如您看到的代码，首先我在检查是否未访问边顶点但错误后将边顶点推送到队列。为了得到正确的答案，如果组合值小于顶点权重，我必须在检查值后 heappush。这是为什么？

 for edge in current.edge_list:
            if edge.to_vertex.is_not_visited():
         ## I first appended the to_vertex to the queue, but it does not work
                total_weight = current_weight + edge.weight
                if total_weight < edge.to_vertex.key:
                    heapq.heappush(queue, edge.to_vertex)
                    edge.to_vertex.key = total_weight
                    edge.to_vertex.parent = current
                    current.visited = True

Answer 1

我假设您已经在顶点 class 中定义了 __lt__ 以供 heapq 使用。每当您更改顶点的 key 属性值时，将距离信息存储为属性可能会破坏您的最小堆不变量。在您的代码片段中，我没有看到任何 re-establishes 不变量。

解释： 虽然 to_vertex 在你的最小堆中和以前一样在同一个地方，你可能已经改变了它的键使其小于它的 parent 或大于其任何 children。当您检查 total_weight < edge.to_vertex.key.

时，只有前者可能会发生

建议： 使用元组的最小堆 (<key>, <vertex>)。

以下内容也可能有助于解决您的代码的其他一些问题：

当heapq.heappop(queue)returnscurrent时，首先要检查是否已经访问过。如果没有，将其标记为已访问，即 current.visited = True，然后 then 迭代出边（即 for edge in current.edge_list: ...）。我们检查 current 是否已经被访问过，因为在 queue.
每当 total_weight < edge.to_vertex.key 时，您必须将 edge.to_vertex 推入您的最小堆。这是因为你刚刚找到了通过current到达这个顶点的更短的方法。当然，你已经知道了。
考虑代码中语句 heapq.heappush(queue, edge.to_vertex) 和 edge.to_vertex.key = total_weight 的顺序。在更新其权重之前，您正在将 to_vertex 推入 queue 。如果你按照上面的建议使用最小堆的元组，这个问题就会消失。

当合并权重小于节点权重时，为什么要放入队列？

What is the reason to put in the queue when the combined weight is less than the node weight?

python

algorithm

dijkstra