python - 关于图数据结构的问题: set of tuples vs dict

Question

下面的代码，我使用元组集来构建图形，将返回-1(解决方案存在，但返回错误的-1):

def findCheapestPrice(self, n, flights, src, dst, K):
    """
    :type flights: List[List[int]]
    :type src: int
    :type dst: int
    :type K: int
    :rtype: int
    """

    # NOTE: Here I use a set
    g = collections.defaultdict(set)
    for s, d, cost in flights:
        g[s].add((cost, d))

    q, distance = [(0, 0, src)], {}
    heapq.heapify(q)
    while q:
        cost, stop, city = heapq.heappop(q)

        if stop>K+1 or cost>distance.get((stop, city), float('inf')): continue

        if city == dst:
            return cost
        for nbr, c in g.get(city, ()):
            if c+cost < distance.get((stop+1, nbr), float('inf')):
                distance[(stop+1, nbr)] = c+cost
                heapq.heappush(q, (c+cost, stop+1, nbr))
    return -1

但是如果我将图形数据结构更改为 dict of dict，则代码可以工作。我已经彻底检查了差异，但仍然找不到答案。是什么造成了差异？

def findCheapestPrice(self, n, flights, src, dst, K):
    """
    :type flights: List[List[int]]
    :type src: int
    :type dst: int
    :type K: int
    :rtype: int
    """

    # NOTE: Here I use a dict
    g = collections.defaultdict(dict)
    for s, d, cost in flights:
        g[s][d]=cost

    q, distance = [(0, 0, src)], {}
    heapq.heapify(q)
    while q:
        cost, stop, city = heapq.heappop(q)

        if stop>K+1 or cost>distance.get((stop, city), float('inf')): continue

        if city == dst:
            return cost
        for nbr, c in g[city].items():
            if c+cost < distance.get((stop+1, nbr), float('inf')):
                distance[(stop+1, nbr)] = c+cost
                heapq.heappush(q, (c+cost, stop+1, nbr))
    return -1

Answer 1

g[s].add((cost, d))

这就是使用元组时初始化数据结构的方式。您可以使用您的城市 s 为您的字典建立索引，然后您将输出一组元组。每个元组都将 cost 作为第一个元素。

当你像这样迭代它时:

for nbr, c in g.get(city, ()):

nbr 是您的cost，因为它是元组中的第一个元素。

g[s][d]=cost

这就是使用字典时初始化数据结构的方式。请记住，此处您使用 cost 作为您的值。

当你像这样迭代它时:

for nbr, c in g[city].items():

c 是您的成本，因为 nbr 与 key 相关联，而 c 与您的值(即成本)相关联。

总之，nbr 和 c 混淆了。在元组的变体中，成本分配给nbr，而在字典的变体中，成本分配给c。