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

Question

我在 Python 中实现了两种 Dijkstra 算法(方法)，第一种方法是从 http://jpython.blogspot.com/2015/10/dijkstra-algorithm.html 中获取的。 source，第二个是我创建的，它更适合 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))

Answer 1

您的代码中有 3 个问题:

• 正如 chrisz 已经指出的那样，您需要将 v 添加到您的队列中，否则您只会在循环中执行一次传递。

• 由于 dist 中的值是在将节点放入队列时更新的，而不是在弹出节点时更新的，因此您需要在一开始就更改源的距离

• 最后1e9和-1的转换没有进行，因为需要用x==1e9代替x 是 1e9。

您可以 checkin 任何符合以下条件的 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]