如何将基于 "None" 距离的 Dijsktra 算法的 Python 实现转换为 "Infinity" 距离

Question

我在 Python 中实现了两个 Dijkstra 算法（方法），第一个方法是我从这个 http://jpython.blogspot.com/2015/10/dijkstra-algorithm.html 来源中获取的，第二个是我创建的，它更适合 C++ 风格（检查和放松）-我喜欢的方法。第一个 Dijkstra 方法有效，但第二个 dijkstra2 总是 returns 1e9。第二种方法有什么问题。

from heapq import *

def Dijkstra(graph, source):
     dist = [None] * len(graph)
     queue = [(0, source)]
     while queue:
          c_dist, u = heappop(queue)
          if dist[u] is None:
               dist[u] = c_dist
               for v, length in graph[u].items():
                    if dist[v] is None:
                         heappush(queue, (c_dist + length, v))

     return [-1 if x is None else x for x in dist]


def dijkstra2( graph, source):
     dist = [1e9] * len(graph)
     queue = [(0, source)]
     while queue:
          c_dist, u = heappop(queue)
          if c_dist > dist[u]:
               continue
          for v, length in graph[u].items():
               if dist[v] > dist[u] + length:
                    dist[v] = dist[u] + length
     return [-1 if x is 1e9 else x for x in dist]


graph = {
  0: { 1:2, 2:4, 3:1 },
  1: { 2:1, 3:3 },
  2: { 4: 7},
  3: { 2: 2 },
  4: { 0:2, 3:3 }, 
  5: {}
}
source = 0

print (Dijkstra(graph, source))

Answer 1

您的代码有 3 个问题：

正如 chrisz 已经指出的那样，您需要将 v 添加到您的队列中，否则您将只执行一次循环。
由于 dist 中的值是在将节点放入队列时更新的，而不是在弹出节点时更新的，因此您需要在开始时更改源的距离
最后没有进行1e9和-1的转换，因为需要用x==1e9代替x is 1e9。

您可以签入任何 python 控制台：

x=1e9 
x is 1e9

returns False.

这是一个完整的工作代码：

def dijkstra2( graph, source):
     INFINITY = 1e9
     dist = [INFINITY] * len(graph)
     queue = [(0, source)]
     dist[source]=  0
     while queue:
          c_dist, u = heappop(queue)
          if c_dist > dist[u]:
               continue
          for v, length in graph[u].items():
               if dist[v] > dist[u] + length:
                    dist[v] = dist[u] + length
                    heappush(queue, (dist[v], v))
     return [-1 if x==INFINITY else x for x in dist]

如何将基于 "None" 距离的 Dijsktra 算法的 Python 实现转换为 "Infinity" 距离

How to convert Python implementation of Dijsktra algorithm based on "None" distances to "Infinity" distance

algorithm

graph

dijkstra

python-3.x