递归实现的Dijkstra算法单次调用正常，循环调用时触发min()空序列错误问题排查

你遇到的问题核心是Python中可变默认参数的特性——你的shortestpath函数里的visited=[]这个默认参数，在函数定义时就会被初始化一次，而不是每次调用函数时重新创建。这就导致当你在for循环中多次调用shortestpath时，visited列表会累积之前调用时添加的节点，最终在后续调用里，所有节点都被标记为已访问，unvisiteds变成空字典，调用min()自然就抛出了ValueError。

举个简单的例子就能验证这个特性：

def test_func(lst=[]):
    lst.append(1)
    print(lst)

test_func()  # 输出 [1]
test_func()  # 输出 [1, 1]，而不是预期的 [1]

修复方案 #

你需要把可变默认参数替换成不可变的默认值（比如None），然后在函数内部初始化可变对象。修改你的shortestpath函数如下：

def shortestpath(graph, start, end, visited=None, distances=None, predecessors=None):
    """Find the shortest path btw start & end nodes in a graph"""
    # 初始化可变参数，避免默认参数复用
    if visited is None:
        visited = []
    if distances is None:
        distances = {}
    if predecessors is None:
        predecessors = {}
    
    # detect if first time through, set current distance to zero
    if not visited:
        distances[start] = 0
    # if we've found our end node, find the path to it, and return
    if start == end:
        path = []
        while end != None:
            path.append(end)
            end = predecessors.get(end, None)
        return distances[start], path[::-1]
    # process neighbors as per algorithm, keep track of predecessors
    for neighbor in graph[start]:
        if neighbor not in visited:
            neighbordist = distances.get(neighbor, float("inf"))
            tentativedist = distances[start] + graph[start][neighbor]
            if tentativedist < neighbordist:
                distances[neighbor] = tentativedist
                predecessors[neighbor] = start
    # neighbors processed, now mark the current node as visited
    visited.append(start)
    # finds the closest unvisited node to the start
    unvisiteds = dict((k, distances.get(k, float("inf"))) for k in graph if k not in visited)
    # 新增判断：如果没有未访问节点，说明无法到达end，可按需处理
    if not unvisiteds:
        return (float("inf"), [])  # 或者抛出异常，根据业务逻辑调整
    closestnode = min(unvisiteds, key=unvisiteds.get)
    # now take the closest node and recurse, making it current
    return shortestpath(graph, closestnode, end, visited, distances, predecessors)

额外优化建议 #

1. 新增了unvisiteds为空的判断逻辑，避免在无法到达目标节点时直接崩溃，你可以根据实际需求调整返回值或者抛出特定异常。
2. 把所有可变默认参数都改成了None初始化的方式，彻底避免了多次调用时的状态污染问题。

现在再运行你的djikstra函数，就不会再出现ValueError了，每次循环调用shortestpath都会使用全新的visited、distances和predecessors对象。

内容的提问来源于stack exchange，提问作者nemo