递归。在给定起点和最大距离的情况下找到所有最长的路径

debugcn 发表于 Dev

用户000

给定起点A和最大距离D，从A开始的最长路径是什么，长度大于或等于D。这段代码有什么问题？

def find_paths(graph, start, path, allpaths, dmax):
    if dmax == 0:
        allpaths.append([start])
    else:
        path.append(start)
        for edge in graph[start]:
            d = graph[start][edge]
            if dmax - d >= 0:
                find_paths(graph, edge, path, allpaths, dmax - d)
            else:
                allpaths.append(path)
    return allpaths

graph = { 
          1: {2: 33, 3: 15},
          2: {1: 33, 4: 57, 5: 7},
          3: {1: 15},
          4: {2: 57},
          5: {1: 89, 2: 7},
        }

print find_paths(graph, 1, [], [], 50)

这给出了：

[[1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3]]

来自的输出find_paths(graph, 1, [], [], 50)应为（1、3）和（1、2、5）。也就是说，两条路径分别通过第一个顶点1和3，第二个顶点1、2和5。

谢谢你。

艾米·泰加登（Amy Teegarden）

一个大问题是您要追加到路径，然后将其传递给递归的下一个迭代。这就是为什么您在每条路径上都得到相同结果的原因。您每次都需要创建一个新路径。

def find_paths(graph, start, path, allpaths, dmax):
    if dmax == 0:
        allpaths.append([start])
    else:
        newpath = path + [start]
        for edge in graph[start]:
            d = graph[start][edge]
            if dmax - d >= 0:   
                find_paths(graph, edge, newpath, allpaths, dmax - d)
            else:
                allpaths.append(newpath + [edge])
    return allpaths

graph = { 
          1: {2: 33, 3: 15},
          2: {1: 33, 4: 57, 5: 7},
          3: {1: 15},
          4: {2: 57},
          5: {1: 89, 2: 7},
        }

print find_paths(graph, 1, [], [], 50)

此外，我不确定为什么您期望结果为（1、3）和（1、2、5）。在我看来（1，3）的长度为15。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。