Python Dijkstra算法 [英] Python Dijkstra Algorithm

问题描述

我正在尝试编写Dijkstra的算法，但是我在为如何在代码中说出某些内容而苦苦挣扎。
为了可视化，这是我要使用数组表示的列：

I am trying to write Dijkstra's Algorithm, however I am struggling on how to 'say' certain things in code. To visualize, here are the columns I want represented using arrays:

   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

因此，将有几个数组，如下面的代码所示：

So, there will be several arrays, as seen in my code below:

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

黑体字是我坚持的地方-我正在尝试实现算法的这一部分：

The part in bold is where I am stuck on - I am trying to implement this section of the algorithm:

3。对于当前节点，请考虑其所有未访问的邻居并计算其暂定距离。例如，如果当前节点（A）的距离为6，并且将其与另一个节点（B）相连的边为2，则通过A到B的距离将为6 + 2 = 8。如果该距离小于以前记录的距离，则覆盖距离

4.完成考虑当前节点的所有邻居后，将其标记为已访问。访问过的节点将不再被检查；现在记录的距离是最终的和最小的

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

I think I am on the right track, i'm just stuck on how to say 'start at a node, get the length from source to a node, if length is smaller, overwrite previous value, then move to next node

推荐答案

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

First, I assume this is a homework problem, as the best suggest is to not bother writing it yourself, but to find an existing implementation on the web. Here's one that looks pretty good, for example.

假设您需要重新发明轮子，那里引用的代码将使用字典来存储节点数据。因此，您可以输入以下内容：

Assuming you do need to reinvent the wheel, the code referenced there uses dictionaries to store the node data. So you feed it something like:

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

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

This seems a more intuitive way of presenting your graph information. Visited nodes and distances can be kept in dictionaries as well.

这篇关于Python Dijkstra算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！