我正在尝试编写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。完成考虑当前节点的所有邻居后,将其标记为已访问。访问过的节点将不再被检查;现在记录的距离是最终的和最小的
我认为我走在正确的轨道上,我只是停留在怎么说:“从节点开始,获取从源到节点的长度,如果长度较小,则覆盖先前的值,然后移至下一个节点
首先,我认为这是一个作业问题,因为最好的建议是不要自己去写,而是在网络上找到现有的实现。 例如,这看起来不错。
假设您 确实 需要重新设计轮子,那么那里引用的代码将使用字典来存储节点数据。因此,您可以输入以下内容:
{ '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} }
这似乎是呈现图形信息的更直观的方法。访问的节点和距离也可以保存在字典中。