扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最短路径困难
单选题
2014年5月第41题
收藏
分享
#数学与经济管理
#最短路径
#第二版教材
#凯恩建议必须掌握
下面的网络图表示从城市A到城市B运煤的各种路线。各线段上的数字表示该线段运煤所需的费用（百元/车）。城市A有三个装货点，城市B有三个卸货点，各点旁标注的数字表示装/卸煤所需的费用（百元/车）。根据该图，从城市A的一个装卸点经过一条路线到城市B的一个卸货点所需的装、运、卸总费用至少为（__）（百元/车）。
问题（1）
正确答案A
凯恩解析
本题考察的是图论中的最短路径问题，适用于Dijkstra 算法进行求解。
我们需要从A 边的装货点（3个）中的任意一个出发，通过中间路线，到达B 边的任意一个卸货点（3个），使得总费用最小。总费用 = 起点装货费用 + 所经路径费用总和 + 终点卸货费用。
红字所在的节点是它所在前驱节点加上费用的最小值。挨个迭代直到终点。这里记得要把最后卸货的梳理算上，就是17+2=19。