python-3.x - 如何将基于“非”距离的Dijkstra算法的Python实现转换为“无限”距离

我在Python中实现了两种Dijkstra算法（方法），第一种方法是从这个“AA>源”中获取的，第二种方法是由我创建的，它更适合C++风格（带有检查和放松）——我更喜欢的方法。第一个Dijkstra方法有效，但第二个dijkstra2始终返回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))

最佳答案

代码中有3个问题：
正如chrisz已经指出的，您需要将v添加到队列中，否则您将只在循环中执行一次传递。
因为dist中的值是在将节点放入队列时更新的，而不是在弹出节点时更新的，所以您需要在开始处更改源的距离
由于需要使用1e9而不是-1，因此不会在结尾执行x==1e9和x is 1e9之间的转换。
您可以签入任何符合以下条件的python控制台：

x=1e9
x is 1e9

返回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]