Dijkstra算法

Question

在阅读Dijkstra算法时，我发现您应该实现min heap。我尝试实现一个最小堆，算法起作用了，但当我不使用最小堆函数，而只是在索引0处弹出顶点时，它也起作用。

我搞不懂为什么当我们要探索堆中的所有顶点时，我们总是需要选择距离最小的顶点进行下一步探索。

例如：

from heapq import heappop, heappush
from math import inf

graph = {
        'A': [('B', 10), ('C', 3)],
        'C': [('D', 2)],
        'D': [('E', 10)],
        'E': [('A', 7)],
        'B': [('C', 3), ('D', 2)]
    }


def dijkstras(graph, start):
  distances = {}
  
  for vertex in graph:
    distances[vertex] = inf
    
  distances[start] = 0
  vertices_to_explore = [(0, start)]
  while vertices_to_explore:
    current_distance, current_vertex = heappop(vertices_to_explore) # this piece of code
    #current_distance, current_vertex = vertices_to_explore.pop(0) # vs. this piece of code
    for neighbor, edge_weight in graph[current_vertex]:
      new_distance = current_distance + edge_weight
      
      if new_distance < distances[neighbor]:
        distances[neighbor] = new_distance
        heappush(vertices_to_explore, (new_distance, neighbor))
        
  return distances
        
distances_from_d = dijkstras(graph, 'D')
print("\n\nShortest Distances: {0}".format(distances_from_d))

当pop(0)的效果相同时，为什么要使用heappop...是因为运行时的原因吗？如果是这样，为什么它运行得更快？

谢谢

Answer 1

该算法适用于vertices_to_explore.pop(0)的原因纯粹是运气。在最小堆中，最小的条目总是在零位置。因此，如果vertices_to_explore是一个合适的堆，那么返回的元素是相同的，无论您使用的是pop(0)还是heappop。

重要的是在那之后会发生什么。heappop将维护堆属性。pop(0)不会这么做的。您的图(以及堆)足够小，因此两个方法在堆上的操作将几乎相同。但是，一旦图形增长，堆的非堆积性将破坏算法，pop(0)变体将返回错误的结果。

Answer 2

由于Dijkstra算法以贪婪的方式工作，我们使用最小堆，并在每一步中取距离最小的顶点；没有比当前步骤中距离最近的顶点的路径更短的路径。这是正确的，因为所有的距离都是正数。

在上面的代码中，常规未排序列表的pop(0)与堆的heappop()的工作方式相同，这与作为输入的图形上的巧合有关(而不是算法)。

Answer 3

按照我们实现minheaps的方式，最小的项在概率上更接近索引0。这意味着，如果堆推送重新堆积列表，索引0处的弹出可能会接近小输入集的最小值idk，但如果没有heappop，它将不会给你任何保证，而且它肯定不再是dijkstras算法。(它甚至可能无法保证正常工作，但在我有时间进行验证之前，这只是一种猜测)。

它可能更快，因为零点的弹出可以在O(1)时间内完成(可能根据实现而摊销)，而堆弹出只保证O(log )。然而，对于非常大的图，heappop可能会给你更好的机会更快地找到最短路径(以及正确性保证)，从而在检查了顶点总数的较小部分之后终止算法。因为虽然检查所有顶点和边确实是最坏的情况，但最好的情况要好得多。