关于图形数据结构的问题：一组元组与字典

Question

我使用一组元组构建图形的以下代码将 return -1（解决方案存在但 return 错误 -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 与密钥相关联，而 c 与您的值相关联，即费用。

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

关于图形数据结构的问题：一组元组与字典

questions on graph data structure: set of tuples vs dict

python

dijkstra