动态规划实现的最短路径算法报错：递归深度超限问题排查

问题分析 #

• 递归循环触发栈溢出：无向图中未标记已访问节点，递归调用会在相邻节点间无限循环（比如A→B→A→B...），直接触发最大递归深度错误。
• costs字典键类型错误：用列表作为字典键，而列表是不可哈希类型，实际运行会抛出TypeError: unhashable type: 'list'，只是栈溢出错误先出现。
• 最短路径判断逻辑颠倒：代码中判断costs[i] + weight(...) > minimum_cost时更新路径，这会选到开销更大的路径，逻辑完全错误。
• 未处理无法到达目标的路径：当某条分支无法到达目标时，代码处理不严谨，可能导致空路径干扰结果。

修复方案 #

1. 添加已访问节点标记：递归时传入visited集合，避免重复访问节点，打破循环递归。
2. 替换costs字典的键类型：将路径转为字符串形式作为键，或者直接把路径和开销合并存储在memo中，简化逻辑。
3. 修正最短路径选择逻辑：将判断条件改为总开销小于当前最小值时更新路径。
4. 优化递归终止与路径处理：明确处理无法到达目标的情况，过滤无效分支。

修复后的完整代码 #

class Graph:
    def __init__(self):
        self.nodes = dict()

    def add_edge(self, p, c, weight):
        if self.nodes.get(p, -1) == -1 or self.nodes.get(c, -1) == -1:
            return
        self.nodes[p].append((c, weight))
        self.nodes[c].append((p, weight))

    def add_node(self, n):
        if self.nodes.get(n, -1) != -1:
            return
        self.nodes[n] = []

    def is_adjacent(self, a, b):
        for i in self.nodes[a]:
            if i[0] == b:
                return True
        return False


def weight(graph, a, b):
    if not graph.is_adjacent(a, b):
        return None  # 用None替代字符串，更便于数值判断
    for i in graph.nodes[a]:
        if i[0] == b:
            return i[1]


def path_length(graph, path):
    total = 0
    for i in range(len(path) - 1):
        w = weight(graph, path[i], path[i+1])
        if w is None:
            return None
        total += w
    return total


memo = dict()  # 键格式："root,target,visited_str"，值为(最短路径, 路径开销)

def shortest_path(graph, root, target, visited=None):
    # 初始化已访问集合
    if visited is None:
        visited = set()
    # 生成唯一的memo键，包含已访问节点信息
    visited_str = ','.join(sorted(visited))
    memo_key = f"{root},{target},{visited_str}"
    
    # 检查缓存
    if memo_key in memo:
        return memo[memo_key][0]
    
    # 终止条件：到达目标节点
    if root == target:
        path = [root]
        memo[memo_key] = (path, 0)
        return path
    
    # 标记当前节点为已访问，避免循环
    visited.add(root)
    
    min_cost = float('inf')
    best_path = []
    
    # 遍历所有相邻节点
    for neighbor, w in graph.nodes[root]:
        if neighbor in visited:
            continue  # 跳过已访问节点
        
        # 递归获取相邻节点到目标的最短路径
        sub_path = shortest_path(graph, neighbor, target, visited.copy())
        if not sub_path:
            continue  # 该分支无法到达目标，跳过
        
        # 计算当前路径的总开销
        sub_cost = path_length(graph, sub_path)
        if sub_cost is None:
            continue
        total_cost = sub_cost + w
        
        # 更新最短路径
        if total_cost < min_cost:
            min_cost = total_cost
            best_path = [root] + sub_path
    
    # 缓存结果
    memo[memo_key] = (best_path, min_cost)
    return best_path


# 测试用图
nodes_ = {
    'A': [('B', 4), ('H', 8)],
    'B': [('A', 4), ('C', 8), ('H', 11)],
    'C': [('B', 8), ('D', 7), ('F', 4), ('I', 2)],
    'D': [('C', 7), ('E', 9), ('F', 14)],
    'E': [('D', 9), ('F', 10)],
    'F': [('C', 4), ('D', 14), ('E', 10), ('G', 2)],
    'G': [('F', 2), ('H', 1), ('I', 6)],
    'H': [('A', 8), ('B', 11), ('G', 1), ('I', 7)],
    'I': [('C', 2), ('G', 6), ('H', 7)]
}

g = Graph()
g.nodes = nodes_

# 调用测试
result = shortest_path(g, 'A', 'I')
print("最短路径:", result)
print("路径长度:", path_length(g, result))

修复说明 #

• 已访问标记：通过visited集合记录已走过的节点，递归时传递集合副本，避免不同分支互相干扰。
• memo缓存优化：将已访问节点信息加入缓存键，确保不同访问路径的缓存不会冲突。
• 类型修正：把weight函数的返回值改为None替代字符串，更适合数值计算，避免类型错误。
• 逻辑修正：正确判断总开销小于当前最小值时更新路径，确保找到最短路径。

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