扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最短路径困难
单选题
2014年5月第41题
收藏
分享
#数学与经济管理
#最短路径
#第二版教材
#凯恩建议必须掌握
下面的网络图表示从城市A到城市B运煤的各种路线。各线段上的数字表示该线段运煤所需的费用(百元/车)。城市A有三个装货点,城市B有三个卸货点,各点旁标注的数字表示装/卸煤所需的费用(百元/车)。根据该图,从城市A的一个装卸点经过一条路线到城市B的一个卸货点所需的装、运、卸总费用至少为(__)(百元/车)。

问题(1)
正确答案A
凯恩解析
本题考察的是图论中的最短路径问题,适用于Dijkstra 算法进行求解。
我们需要从A 边的装货点(3个)中的任意一个出发,通过中间路线,到达B 边的任意一个卸货点(3个),使得总费用最小。总费用 = 起点装货费用 + 所经路径费用总和 + 终点卸货费用。

红字所在的节点是它所在前驱节点加上费用的最小值。挨个迭代直到终点。这里记得要把最后卸货的梳理算上,就是17+2=19。
