最少费用购物问题代码

最小费用路径（Minimum Cost Spanning Tree，MST）问题是图论中常见的优化问题，通常涉及在一个加权图中找到一棵树，这棵树包含所有节点，且边的总权重尽可能小。一个经典的算法是Prim算法或Kruskal算法。

Prim算法是从一个初始顶点开始，逐步添加与其相连的边，每一步都选择当前生成树中最便宜的新边，直到覆盖所有节点。Python代码示例如下：

import heapq

def prim(graph, start):
    mst = {start: 0}
    visited = set()
    edges = [(cost, u, v) for u in graph for v, cost in graph[u].items() if v not in visited]
    
    while edges:
        min_cost, current_node, next_node = heapq.heappop(edges)
        
        # 如果边已经存在于 MST 中，跳过
        if min_cost > mst.get(next_node, float('inf')):
            continue
        
        visited.add(current_node)
        mst[next_node] = min_cost
        for neighbor, cost in graph[current_node].items():
            if neighbor not in visited:
                heapq.heappush(edges, (cost, next_node, neighbor))
                
    return mst

# 使用示例
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4},
    'D': {'B': 1, 'C': 4}
}

mst = prim(graph, 'A')
print("最小费用树:", mst)

Kruskal算法则按照边的权重从小到大排序，每次选取两个不形成环的边加入树中，直到有n-1条边。这两个算法都是解决最小费用生成树的有效手段。