返回
当前 - 选择题 - 最短路径中等
题号：0120170500041
单选题
2017年5月第41题
中等
题号：0120170500041
单选题
2017年5月第41题
最短路径
困难
高频
加工某种零件需要依次经过毛坯、机加工、热处理和检验四道工序。各道工序有多种方案可选，对应不同的费用。下图表明了四道工序各种可选方案（连线）的衔接关系，线旁的数字表示该工序加工一个零件所需的费用（单位：元）。从该图可以推算出， 加工一个零件的总费用至少需要（130）元。
问题（1）
浓缩知识点
多阶段决策类的最小成本问题，可通过分层递推最优解的思路解决。核心逻辑是按阶段从起点到终点，逐个计算每个节点的最小累计成本——每个节点的最优值仅由前一阶段所有可连通节点的最小成本推导得出，无需枚举全部路径，能有效提升求解效率。这类方法属于动态规划或分层图最短路径算法的应用范畴，除了工序成本计算，还可拓展用于路径规划、项目工期优化、资源分配等多领域，本质是通过局部最优的逐步累积，实现全局最优的求解。
正确答案
B
本题考察的是最短路径（分层图/用Dijkstra或动态规划） 的求解方法。
思路是自左向右逐层累计最小费用，直到终点I。
起点A到各中间点的最小费用：到B为50，到C为40。
到机加工层：到D=min(50+30, 40+40)=80；到E=min(50+40, 40+60)=90；到F=min(50+40, 40+40)=80。
到热处理层：到G=min(80+40, 90+20, 80+40)=110（经E最优）；到H=min(80+50, 90+40, 80+50)=130。
到终点I：min(110+20, 130+10)=130。
因此最短路径可为A→B→E→G→I，总费用50+40+20+20=130元。
因此，最小总费用为130元。