目标是创建一个名为siz的数组,该数组存储来自起始节点的所有路径的长度。在理想情况下,我会调用f(start)并期望图中所有顶点v的siz[v]都被填满
这就是我正在使用的算法
def f (node):
vis[node] = 1
for elem in adj[node]:
if vis[elem]==0:
for i in siz[node]:
siz[elem].append(i + w[(node,elem)])
f(elem)
变量描述:
递归似乎不正确,我不知道何时实际将节点标记为已访问。此外,由于存在循环,我不希望距离包含循环。例如,A->;B->;C->;A->;D完全不应该是这样。它应该只是一个->;D或所有其他方式有一条从a到D的路径,没有经过循环
要举例说明此算法如何无法按预期工作,请执行以下操作:
如果我将节点和边权重输入为w(1,2)=1,w(2,3)=2,w(2,4)=7和w(3,4)=1
然后siz=[-1]、[0]、[1]、[3]、[4]]。(请注意,我最初设置了siz[1]=0和siz[0]=-1,因为我的起始节点是1,数组是0索引的,但我需要它作为1索引),而理想的siz应该是[[-1]、[0]、[1]、[3,9]、[4,8]]
siz
的“node_paths
”。 然后对每个邻居递归由于给
f
(参见下面的代码)的路径是一个副本,因此您不必手动删除添加的节点 (但是,如果您使用path.append(node)
,当您退出f
时,您将不得不path.pop()
)在上面的代码中,我存储了路径和加权和以简化调试,但您显然可以放弃存储的路径
有几点:
相关问题 更多 >
编程相关推荐