Whyt是Dijkstra与堆O（v）而不是（v＆＃x2b; e）的空间复杂性吗？

Question

关于dijkstra，带有最小堆（优先队列），

import heapq

graph = [
  [(1, 5), (2, 3)],
  [(3, 3), (2, 2)],
  [(4, 4), (5, 2), (3, 7)],
  [(4, 1)],
  [],
  [(4, 5)]
]
v = len(graph)
dist = [math.inf] * v

def dijkstra(start):
  # Init dist / heap / heap with start
  dist[start] = 0
  hq = [(0, start)]

  while hq:
    # pop current shortest distance node
    d, cur = heapq.heappop(hq) 
    if d > dist[cur]: continue # pass decided node
      
    for next, weight in graph[cur]:
      new_dist = dist[cur] + weight
      if new_dist < dist[next]:
        dist[next] = new_dist
        heapq.heappush(hq, (new_dist, next))

  for i in range(v): print(dist[i], end=" ") # print distance
      

我知道存储距离需要O（v）。 但是堆不需要o（e），因为它包含总共E？

因此，我认为空间复杂性是O（V+E）。 有什么问题吗？

谢谢

Answer 1

O（v）是Dijkstra实现的空间复杂性，该实现使用了带有减少键操作的堆，并使用降低 - 键来更新现有的堆条目，而不是为同一节点添加多个条目。通过这样的实现，堆每个顶点最多将有一个条目，而不是每个边缘的一个条目。