0

我在 python 中使用了一个简单的 heapq,并在其上实现了lt函数的自定义元素。

class Edge:
    def __init__(self, cost, u, v):
        self.u = u
        self.v = v
        self.cost = cost
    def weight(self):
        w = self.cost
        v = self.v
        while v.parent is not None:
            w += v.const
            v = v.parent
        return w

    def __lt__(self, other):
        return self.weight() < other.weight()

然后我在另一个名为 P 的数组中保留一堆这些元素:

class Vertex:
    def __init__(self, node=None):
        #other stuff omited ##### 
        self.P = []

    def add_incoming_nodes(self, subgraph):
        for node, costs in subgraph.items():
            #if costs[self.vertex] is not 0: #node is not self
            #push endpoints of the edge from another vertex to this vertex
            heapq.heappush(self.P, Edge(costs[self.vertex], node, self))

问题是当我堆放一个元素时,我希望它是我数组中的最小元素,对吗?但是这个断言在这里失败了

#select arbitrary vertex
a = all_nodes[0]
while a.P: #while P[a] is not ∅
    edge = heapq.heappop(a.P)
    for a_edge in a.P: 
        assert edge.weight() < a_edge.weight()
4

0 回答 0