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

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

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

解释:而to_vertex与之前在最小堆中的位置相同，您可能已将其 key 更改得足以小于其父项或大于其任何子项。当您检查 total_weight < edge.to_vertex.key 时，只有前者可能会发生.

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

以下内容也可能有助于修复您的代码的其他一些问题:

1. 当 heapq.heappop(queue)返回 current ，你首先必须检查它是否已经被访问过。如果没有，将其标记为已访问，即 current.visited = True , 和 then 迭代出边(即 for edge in current.edge_list: ... )。我们检查是否 current已经访问过，因为在 queue 中可能有该顶点的多个条目.

2. 每当total_weight < edge.to_vertex.key , 你必须推 edge.to_vertex进入你的最小堆。这是因为你刚刚找到了通过 current 到达该顶点的更短方式.当然，你已经知道了。

3. 考虑语句的顺序 heapq.heappush(queue, edge.to_vertex)和 edge.to_vertex.key = total_weight在你的代码中。您正在插入 to_vertex进入queue 之前更新其权重。如果您按照上面的建议使用元组的最小堆，这个问题就会消失。