Python Dijkstra算法

Question

我正在尝试编写 Dijkstra 算法，但是我在如何用代码“表达”某些内容方面遇到了困难。 为了可视化，以下是我想使用数组表示的列：

   max_nodes  
   A  B  C         Length       Predecessor       Visited/Unvisited
A 0  1   2             -1                                              U
B 1  0   1             -1                                              U
C 2  1   0             -1                                              U

因此，将会有几个数组，如下所示：

def dijkstra (graph, start, end)

network[max_nodes][max_nodes]
state  [max_nodes][length]
state2 [max_nodes][predecessor]
state3 [max_nodes][visited]
initialNode = 0

    for nodes in graph:
      D[max_nodes][length] = -1
      P[max_nodes][predecessor] = ""
      V[max_nodes][visited] = false

      for l in graph:

       length = lengthFromSource[node] + graph[node][l]
          if length < lengthFromSourceNode[w]:
             state[l][length] = x
             state2[l][predecessor] 
             state3[l][visited] = true
          x +=1

我卡在粗体部分 - 我正在尝试实现算法的这一部分：

3. 对于当前节点，考虑所有未访问过的邻居并计算它们的临时距离。例如，如果当前节点(A)的距离为6，并且连接它与另一个节点(B)的边长为2，则通过A到B的距离将是6+2=8。如果此距离小于先前记录的距离，则覆盖该距离。
4. 当我们完成考虑当前节点的所有邻居时，将其标记为已访问。已访问的节点不会再次被检查；现在记录的距离是最终和最小的。

我认为我走在正确的轨道上，只是卡在如何表达“从一个节点开始，获取从源到节点的长度，如果长度更短，则覆盖以前的值，然后移动到下一个节点”的部分。

- user612041

---

粗体部分是什么？哪一部分是粗体？ - S.Lott

啊，对不起；从'for l in graph'开始的代码。 - user612041

你的代码并没有多少意义。缩进相当随意，而且存在很多未定义的变量。在编程时，请从一个简单可行的东西开始，并从这里扩展。 - Jochen Ritzel

Answer 1

我使用了一个字典来存储网络数据。数据格式如下： 创建一个网络字典（由用户提供）。

net = {'0':{'1':100, '2':300},
       '1':{'3':500, '4':500, '5':100},
       '2':{'4':100, '5':100},
       '3':{'5':20},
       '4':{'5':20},
       '5':{}
       }

最短路径算法（用户需要指定起点和终点节点）

def dijkstra(net, s, t):
    # sanity check
    if s == t:
        return "The start and terminal nodes are the same. Minimum distance is 0."
    if s not in net:    # python2: if net.has_key(s)==False:
        return "There is no start node called " + str(s) + "."
    if t not in net:    # python2: if net.has_key(t)==False:
        return "There is no terminal node called " + str(t) + "."
    # create a labels dictionary
    labels={}
    # record whether a label was updated
    order={}
    # populate an initial labels dictionary
    for i in net.keys():
        if i == s: labels[i] = 0 # shortest distance form s to s is 0
        else: labels[i] = float("inf") # initial labels are infinity
    from copy import copy
    drop1 = copy(labels) # used for looping
    ## begin algorithm
    while len(drop1) > 0:
        # find the key with the lowest label
        minNode = min(drop1, key = drop1.get) #minNode is the node with the smallest label
        # update labels for nodes that are connected to minNode
        for i in net[minNode]:
            if labels[i] > (labels[minNode] + net[minNode][i]):
                labels[i] = labels[minNode] + net[minNode][i]
                drop1[i] = labels[minNode] + net[minNode][i]
                order[i] = minNode
        del drop1[minNode] # once a node has been visited, it's excluded from drop1
    ## end algorithm
    # print shortest path
    temp = copy(t)
    rpath = []
    path = []
    while 1:
        rpath.append(temp)
        if temp in order: temp = order[temp]    #if order.has_key(temp): temp = order[temp]
        else: return "There is no path from " + str(s) + " to " + str(t) + "."
        if temp == s:
            rpath.append(temp)
            break
    for j in range(len(rpath)-1,-1,-1):
        path.append(rpath[j])
    return "The shortest path from " + s + " to " + t + " is " + str(path) + ". Minimum distance is " + str(labels[t]) + "."

# Given a large random network find the shortest path from '0' to '5'
print dijkstra(net, s='0', t='5')

- William Chiu

---

drop1 = copy(labels) 可以替换为 drop1 = labels.copy()。 - warvariuc

Answer 2

首先，我假设这是一个作业问题，因为最好的建议是不要自己编写代码，而是在网上找到现有的实现。例如，这里有一个看起来很不错的实现。

假设你确实需要重新发明轮子，那么参考该代码使用字典存储节点数据。所以你可以提供以下内容：

{ 
  's': {'u' : 10, 'x' : 5}, 
  'u': {'v' : 1, 'x' : 2}, 
  'v': {'y' : 4}, 
  'x': {'u' : 3, 'v' : 9, 'y' : 2}, 
  'y': {'s' : 7, 'v' : 6}
}

这似乎是展示图形信息的更直观方式。访问过的节点和距离也可以保存在字典中。

- Chris B.

---

嗨 - 感谢您的回复，我被分配的实现方法与互联网上的示例略有不同，因此使用了二维数组 - 我只是不太擅长使用数组。 - user612041

此外，节点信息将从文本文件中提取，因此该部分不适用，尽管我一直在尝试从那个特定的代码中提取一些内容！ - user612041