更新优先级队列python-Dijkstras算法

Question

我想了解在下面的工作和完成的代码中，为什么在更新pq_update时，它被写为pq_update[neighbor][1]。

没有写pq_update[neighbor]（我就是这样做的），它似乎没有改变任何东西，所以为什么要包括它？

谢谢你

import heapq

def dijkstra(graph, start):

  distances = {vertex:float('inf') for vertex in graph}
  pq = []
  pq_update = {}
  distances[start] = 0

  for vertex, value in distances.items():
    entry = [vertex, value]
    heapq.heappush(pq, entry)
    pq_update[vertex] = entry

  while pq:

    getmin = heapq.heappop(pq)[0]

    for neighbour, distance_neigh in graph[getmin].items():
      dist = distances[getmin] + distance_neigh
      if dist < distances[neighbour]:
        distances[neighbour] = dist
        pq_update[neighbour][1] = dist # THIS LINE !!!

  print(distances)
  return distances 


if __name__ == '__main__':

  example_graph = {
      'U': {'V': 2, 'W': 5, 'X': 1},
      'V': {'U': 2, 'X': 2, 'W': 3},
      'W': {'V': 3, 'U': 5, 'X': 3, 'Y': 1, 'Z': 5},
      'X': {'U': 1, 'V': 2, 'W': 3, 'Y': 1},
      'Y': {'X': 1, 'W': 1, 'Z': 1},
      'Z': {'W': 5, 'Y': 1},
  }
  dijkstra(example_graph, 'X')

Answer 1

注意：您的实现被破坏了，不能正确地实现Dijkstra。下面是更多信息。在

pq_update字典包含列表，每个列表有两个条目：

for vertex, value in distances.items():
    entry = [vertex, value]
    heapq.heappush(pq, entry)
    pq_update[vertex] = entry

所以pq_update[neighbour]是一个既有顶点又有距离的列表。您希望更新距离，而不是替换[vertex, value]列表，因此使用pq_update[neighbour][1]。在

请注意，entry列表也是与heapq共享的。pq堆引用了同一个列表对象，因此对pq_update[neightbor][1]的更改也将显示在仍要在堆上处理的条目中！在

当您直接分配给pq_update[neighbour]时，您将移除该连接。在

您看不到任何区别的原因是因为算法的实现实际上是中断的，因为堆没有正确使用。堆是按节点名称排序的，而不是按距离排序，而且当距离改变时，堆也永远不会更新。因为堆的使用不正确，所以总是按字母顺序遍历节点。在

实际上，根本不需要使用堆。实际上，您并没有实现Dijkstra，因为您实际上并没有试图在图中找到两个节点之间的最短路径。而是查找从起始节点到所有其他节点的路径，并找到它们的最短距离。在这种情况下，一个常规的堆栈或队列就可以正常工作了，这正是您在这里所拥有的。在

您可以将函数（使用更好的名称）重写为：

^{pr2}$

这只是简单地以呼吸优先顺序遍历节点并更新找到的距离。在