理解这个深度优先搜索算法

Question

我收到了一个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），递归发生了。此时，递归会一直到达图形的底部，直到它到达没有孩子或目标节点为止。如果到达了不是目标的无子节点，则会忽略基本情况和整个循环，返回none。然后，将该none简单地传递给递归链。如果到达目标节点，则递归的底层实际上返回一个值（路径），该值向上冒泡到递归的顶部。

在那一点上，我感到困惑，因为“shortest”的作用是什么。所以，每次为newPath返回一个实际值时，都会将该值分配给shortest，然后添加到path中。但是，假设我有多条通往目标节点的路径。我成功找到第一条路径，而路径等于所有newPaths/shortests的总和。但是，对于下一次成功到达目标的递归，path不是只会继续添加更多newPaths吗？因此，最终结果会是每条可能到达目标节点的路径列表，而不是最短路径吗？

- user1427661

---

提示：可以用纸笔手动模拟递归调用的过程，以便更好地理解代码的执行流程（最好使用小规模图形作为输入:p）。 - keyser

请注意，建议的算法虽然正确，但效率较低。它会生成到目标的所有路径，并检查哪个路径最好（这样的路径数量是指数级别的）。而寻找最短路径更有效的算法是BFS。 - amit

Answer 1

path变量是局部变量，每个递归调用都有自己的堆栈帧 - 它与其他调用无关。这意味着当下一个调用开始时，一切都是全新的。

- Petar Minchev

---

如果路径在每次函数调用中都是本地的，那么路径的最终值如何计算？如果我一直递归到底部，并且每次回溯调用都计算路径=路径+最短距离，但是路径在每次调用时都被重置，那么Python如何返回一个包含从基本情况到开头的每个节点的值？ - user1427661

看一下 path = path + shortest，shortest 实际上包含了下一个递归调用的路径变量的值。 - Petar Minchev