一尘不染

Python Dijkstra算法

python

我正在尝试编写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。完成考虑当前节点的所有邻居后,将其标记为已访问。访问过的节点将不再被检查;现在记录的距离是最终的和最小的

我认为我走在正确的轨道上,我只是停留在怎么说:“从节点开始,获取从源到节点的长度,如果长度较小,则覆盖先前的值,然后移至下一个节点


阅读 273

收藏
2021-01-20

共1个答案

一尘不染

首先,我认为这是一个作业问题,因为最好的建议是不要自己去写,而是在网络上找到现有的实现。
例如,这看起来不错

假设您 确实 需要重新设计轮子,那么那里引用的代码将使用字典来存储节点数据。因此,您可以输入以下内容:

{ 
  '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}
}

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

2021-01-20