扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最短路径困难
单选题
2014年5月第41题
困难
单选题
2014年5月第41题
#第二版教材
#必须掌握
下面的网络图表示从城市A到城市B运煤的各种路线。各线段上的数字表示该线段运煤所需的费用（百元/车）。城市A有三个装货点，城市B有三个卸货点，各点旁标注的数字表示装/卸煤所需的费用（百元/车）。根据该图，从城市A的一个装卸点经过一条路线到城市B的一个卸货点所需的装、运、卸总费用至少为（__）（百元/车）。
问题（1）
浓缩知识点
迪杰斯特拉算法是求解边权非负的带权图最短路径问题的经典方法，可计算从源点到其他节点的最小累计路径成本。在多起点、多终点的实际应用场景（如物流运输、交通路线规划）中，不能仅计算路径本身的成本，还需将起点的附加成本（如装货费）、终点的附加成本（如卸货费）整合进总费用计算逻辑，通过逐步迭代更新各节点的最小累计成本，最终可得出跨起点终点的总最低成本。
正确答案
A
本题考察的是图论中的最短路径问题，适用于Dijkstra 算法进行求解。
我们需要从A 边的装货点（3个）中的任意一个出发，通过中间路线，到达B 边的任意一个卸货点（3个），使得总费用最小。总费用 = 起点装货费用 + 所经路径费用总和 + 终点卸货费用。
红字所在的节点是它所在前驱节点加上费用的最小值。挨个迭代直到终点。这里记得要把最后卸货的梳理算上，就是17+2=19。