我正在尝试编写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。如果此距离小于先前记录的距离,请覆盖该距离
四。当我们考虑完当前节点的所有邻居时,将其标记为已访问。已访问的节点将不再被检查;它现在记录的距离是最终的和最小的
我想我是在正确的轨道上,我只是停留在如何说'从一个节点开始,得到从源到一个节点的长度,如果长度较小,覆盖上一个值,然后移动到下一个节点
首先,我假设这是一个家庭作业问题,最好的建议是不要费心自己写,而是在web上找到一个现有的实现。Here's one that looks pretty good, for example。
假设您需要重新设计轮子,这里引用的代码使用字典来存储节点数据。所以你给它喂食类似于:
这似乎是一种更直观的表示图形信息的方法。访问的节点和距离也可以保存在字典中。
我还用字典来存储网络。
创建网络词典(用户提供)
最短路径算法(用户需要指定起点和终点节点)
相关问题 更多 >
编程相关推荐