Dijkstra 算法

Question

在阅读 Dijkstra 算法时，我发现您应该实现一个最小堆。我尝试实现一个最小堆并且该算法有效，但是当我不使用最小堆函数而只是从索引 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

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

事实上，在上面的代码中，常规未排序列表的 pop(0) 与堆的 heappop() 工作相同，这与作为输入给出的图上的巧合有关（而不是算法） .

Answer 2

该算法与 vertices_to_explore.pop(0) 一起工作的原因纯属运气。在 min-heap 中，最小的条目始终位于位置零。因此，如果 vertices_to_explore 是适当的堆，则 returned 元素是相同的，无论您使用的是 pop(0) 还是 heappop.

重要的是之后会发生什么。 heappop 将维护堆属性。 pop(0)不会那样做。您的图表（以及堆）足够小，以至于两种方法在堆上的操作几乎相同。但是一旦你的图表增长，你的堆的 non-heapiness 就会破坏算法并且 pop(0) 变体会 return 错误的结果。

Answer 3

我们实现 minheaps 的方式最小的项目将按概率接近索引 0..这意味着对于小输入集，索引 0 处的弹出可能接近最小值，如果堆推送重新堆化列表，idk，但如果没有 heappop，它不会给你任何保证，它肯定不再是 dijkstras 算法。（它甚至可能无法保证正常工作，但在我有时间验证之前，这是推测）。

它可能会更快，因为 0 处的弹出可以在 O(1) 时间内完成（可能根据实现进行摊销），而 heappop 只保证 O(log N)。然而，对于非常大的图，heappop 可能会让您有更好的机会更快地找到最短路径（和正确性保证），从而在检查顶点总数的一小部分后终止算法，而不是其他方式。因为虽然检查所有顶点和边确实是最坏的情况，但最好的情况要好得多。

Dijkstra 算法

Dijkstra’s algorithm

python

algorithm

dijkstra