如何用Python字典计算图中各路径总成本并找出最短路径

你已经能找出从A到F的所有路径，但缺少路径成本计算的逻辑。可以通过修改递归函数，在遍历路径的同时累计每条边的权重，最终得到每条路径的总成本，再筛选出成本最低的路径。

修改后的完整代码 #

graph = {'A': {'B':2, 'C':3},
     'B': {'C':2, 'D':5},
     'C': {'D':4, 'G':2},
     'D': {'C':6, 'E':4},
     'E': {'F':1},
     'F': [],
     'G': []}

def find_all_paths_with_cost(graph, start, end, path=[], current_cost=0):
    path = path + [start]
    if start == end:
        return [(path, current_cost)]
    if start not in graph:
        return []
    paths_with_cost = []
    # 遍历当前节点的所有邻居及对应边权重
    for neighbor, edge_cost in graph[start].items():
        if neighbor not in path:
            # 递归时累加当前边的成本，传递更新后的路径和成本
            paths_with_cost += find_all_paths_with_cost(graph, neighbor, end, path, current_cost + edge_cost)
    return paths_with_cost

# 获取所有路径及对应成本
all_paths = find_all_paths_with_cost(graph, 'A', 'F')

# 打印每条路径和成本
print("所有路径及对应成本：")
for path, cost in all_paths:
    print(f"路径: {' -> '.join(path)}，总成本: {cost}")

# 筛选成本最低的路径
if all_paths:
    shortest_path = min(all_paths, key=lambda item: item[1])
    print("\n成本最低的最短路径：")
    print(f"路径: {' -> '.join(shortest_path[0])}，总成本: {shortest_path[1]}")
else:
    print("不存在从A到F的有效路径")

关键修改说明 #

• 给递归函数新增current_cost参数，用于实时累计路径的总成本
• 遍历节点邻居时，同时获取邻居节点和该边的权重，而不是只遍历节点
• 递归调用时，将当前边的权重加到current_cost上，实现成本的累加
• 到达终点时，返回包含「路径列表」和「总成本」的元组，方便后续处理
• 使用min()函数结合lambda表达式，快速找出成本最低的路径

你之前尝试的硬编码节点成本相加的方式，只能计算单个节点的邻居成本总和，无法适配整条路径的动态累加，所以无法得到正确的路径总成本。

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