实现Dijkstra算法时触发ValueError: too many values to unpack (expected 2)

问题场景 #

运行带权节点和边的Dijkstra最短路径算法时，在语句shortest_path_lenghts, shortest_paths = dijkstra(nodes, edges)处触发错误：

ValueError: too many values to unpack (expected 2)

相关代码：

nodes = ['0', '1', '2', '3', '4', '5', '6', '7'] 
edges = {('0', '1'): 1, ('0', '4'): 1, ('0', '5'): 1, ('1', '2'): 0, ('2', '3'): 0, ('4', '3'): 0, ('5', '6'): 0, ('6', '7'):0, ('7', '3'): 0}

def dijkstra(nodes, edges, source_index=0):
    path_lenghts = {v: float('inf') for v in nodes}
    path_lenghts[source_index] = 0

    adjacent_nodes = {v: {} for v in nodes}
    for (u, v), w_uv in edges.items():
        adjacent_nodes[u][v] = w_uv
        adjacent_nodes[v][u] = w_uv
    
    temporary_nodes = [v for v in nodes]
    while len(temporary_nodes) > 0:
        upper_bounds = {v: path_lenghts[v] for v in temporary_nodes}
        u = min(upper_bounds, key = upper_bounds.get)
        temporary_nodes.remove(u)

        for v, w_uv in adjacent_nodes[u].items():
            path_lenghts[v] = min(path_lenghts[v], path_lenghts[u] + w_uv)
    
    return path_lenghts

shortest_path_lenghts, shortest_paths = dijkstra(nodes, edges)

print(shortest_path_lenghts)
print(shortest_paths)

报错详情：

---> 30 shortest_path_lenghts, shortest_paths = dijkstra(nodes, edges)
     32 print(shortest_path_lenghts)
     34 print(shortest_paths)

ValueError: too many values to unpack (expected 2)

错误原因 #

1. 返回值数量不匹配：你定义的dijkstra函数仅返回一个值path_lenghts（存储各节点到源点的最短路径长度），但调用时试图将返回值拆包赋值给两个变量，Python无法完成这种不匹配的赋值，因此抛出错误。
2. 源节点类型错误：函数默认参数source_index=0是整数，但你的nodes是字符串类型的节点（如'0'），会导致初始化path_lenghts[source_index] = 0时出现键不存在的隐性问题。
3. 缺少路径记录逻辑：当前函数只计算了路径长度，没有实现记录最短路径的逻辑，原本就无法返回shortest_paths。

修复方案 #

修改函数使其同时返回路径长度和路径信息，并修正源节点类型问题：

nodes = ['0', '1', '2', '3', '4', '5', '6', '7'] 
edges = {('0', '1'): 1, ('0', '4'): 1, ('0', '5'): 1, ('1', '2'): 0, ('2', '3'): 0, ('4', '3'): 0, ('5', '6'): 0, ('6', '7'):0, ('7', '3'): 0}

def dijkstra(nodes, edges, source='0'):
    # 初始化路径长度：所有节点设为无穷大，源节点设为0
    path_lengths = {v: float('inf') for v in nodes}
    path_lengths[source] = 0
    # 初始化路径记录：每个节点的完整最短路径
    paths = {v: [] for v in nodes}
    paths[source] = [source]

    # 构建双向邻接表
    adjacent_nodes = {v: {} for v in nodes}
    for (u, v), w_uv in edges.items():
        adjacent_nodes[u][v] = w_uv
        adjacent_nodes[v][u] = w_uv
    
    temporary_nodes = nodes.copy()
    while temporary_nodes:
        # 找到临时节点中路径长度最小的节点
        upper_bounds = {v: path_lengths[v] for v in temporary_nodes}
        u = min(upper_bounds, key=upper_bounds.get)
        temporary_nodes.remove(u)

        # 松弛操作，同步更新路径长度和路径信息
        for v, w_uv in adjacent_nodes[u].items():
            if path_lengths[v] > path_lengths[u] + w_uv:
                path_lengths[v] = path_lengths[u] + w_uv
                paths[v] = paths[u] + [v]
    
    # 返回两个结果：路径长度字典、路径记录字典
    return path_lengths, paths

# 现在可正确接收两个返回值
shortest_path_lengths, shortest_paths = dijkstra(nodes, edges)

print("最短路径长度：")
print(shortest_path_lengths)

print("\n最短路径：")
print(shortest_paths)

修复说明 #

• 将源节点参数改为字符串类型source='0'，匹配节点列表的类型，避免键不存在问题。
• 添加paths字典，用于记录每个节点到源节点的完整最短路径。
• 在松弛操作中，当找到更短路径时同步更新路径记录。
• 函数最终返回两个值，与调用时的变量数量匹配，解决拆包错误。

内容的提问来源于stack exchange，提问作者nic.o