查找最短路径时最大递归深度超出错误

Question

我试图找到从源到目标的最短点，但我收到错误：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)```

Answer 1

2件事：

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

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

shortest_path(source, target, set())

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

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

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