3

我得到了一个 DFS 算法，它返回到目标节点的最短路径。它以图（包含所有节点及其路径）、起始节点、目标节点和已访问节点列表（初始化为空）作为参数。这是代码：

def shortestPath(graph, start, end, visited = []):
    path = str(start)
    if start == end:
        return path
    shortest = None
    for node in graph.childrenOf(start):
        if str(node) not in visited:
            visited = visited + [str(node)]
            newPath = shortestPath(graph, start, end, visited)
            if newPath = None:
                continue
            if shortest == None or len(newPath) < shortest:
                shortest = newPath
    if shortest != None:
         path = path + shortest
    else:
         path = None
    return path

我理解深度优先搜索的概念，但这种递归让我大吃一惊。让我知道我的思路是否完全正确以及我在哪里出轨。

所以基本上，递归发生在 newPath 被赋值时，这当然是对 shortestPath 的调用。在这一点上，递归一直沿着图向下，直到它到达没有子节点的节点或目标节点。如果它到达一个没有子节点且不是目标的节点，则忽略基本情况，并忽略整个 for 循环，返回值为 none。那 None 然后简单地传递到递归链上。如果它到达目标节点，那么递归的底层实际上会返回一个值（路径），该值会冒泡到递归的顶部。

那时我很困惑，因为“最短”是怎么回事。因此，每次为 newPath 返回实际值时，都会为 shortest 分配该值，然后将其添加到 path 中。但是，假设我有多个通往目标节点的路径。我成功找到了第一条路径，路径等于所有新路径/最短路径的总和。但是对于成功达到目标的下一个递归，路径不只是不断添加更多的新路径吗？那么最终结果难道不是我可以访问以到达目标节点的每条路径的长列表，而不是最短路径吗？

4

1 回答 1

3

该path变量是函数的局部变量。每个递归调用都有自己的堆栈框架 - 它独立于其他调用）。这意味着当下一次通话开始时，一切都是全新的。

于 2012-10-10T15:26:03.980 回答