时间戳

首页 > 解决方案 > 寻找最短路径时的最大递归深度超出错误

python - 寻找最短路径时的最大递归深度超出错误

问题描述

我试图找到从源到目标的最短点，但出现错误： RecursionError: maximum recursion depth exceeded while calling a Python object

这是我的代码，其中 neighbors_for_id 返回源邻居的 id 列表：

    """
    Returns the shortest list of person_ids that connect the source to the target.

    If no possible path, returns None.
    """
    visited = set()
    path = []
    if source == target:
        return path
    while source != target:
        destinations = neighbors_for_id(source)
        for neighbor in destinations:
            path.append(neighbor)
            if neighbor == target:
                return path
            if neighbor not in visited:
                visited.add(neighbor)
                source = neighbor
                shortest_path(source, target, visited)```

标签： pythonrecursion

解决方案

2件事：

您当前（错误地）在进入函数时将“已访问”重置为空集，即使您将其作为来自内部调用的参数传递。这可能会导致最大深度问题，因为它现在可以在 2 个邻居之间“乒乓”或跟随图形中的循环。

当您在外部调用该函数以启动它时，只需传递一个空集：

shortest_path(source, target, set())

您正在对路径列表执行类似的操作。您需要在递归中传递它，以便后续步骤将添加到不断增长的列表中，而不是在函数中重置它。因此，您可能最终会得到一个包含路径的新函数签名。

您可以使用默认值对其进行一些清理，例如：

def shortest_path(source, target, visited=set(), path=list() ):

推荐阅读