某公司从甲地向丁地运送物资，运送过程中先后需要经过乙、丙两个中转站，其中乙中转站可以选择乙1和乙2两个可选地点，丙中转站可以选择丙1、丙2和丙3三个可选地点，各相邻两地之间的距离如下表所示，则甲地到丁地之间的最短距离为( )公里。

admin2018-10-14 25

问题某公司从甲地向丁地运送物资，运送过程中先后需要经过乙、丙两个中转站，其中乙中转站可以选择乙1和乙2两个可选地点，丙中转站可以选择丙1、丙2和丙3三个可选地点，各相邻两地之间的距离如下表所示，则甲地到丁地之间的最短距离为( )公里。

选项 A、64
B、74
C、76
D、68

答案B

解析这题考的是两点之间的最短路径问题。
将表格转换成网络图，这题就相当于求网络图的最短路径了，注意，跟关键路径法不同，关键路径法是求网络图的最长路径。

如果你仍然不能目测找到最短路径，也可以将上图合并简化(利用Dijkstra最短路径算法的思想：最短路径的任意一段都是局部最优的)，简化成如下的3层图。

显然，网络图的最短径是：甲→丙1→丁(全路径是甲→乙1→丙1→丁)，甲地到丁地之间的最短距离为74公里。
有同学说，我最熟悉关键路径法了，能不能用32(原图中的最大数字)减去所有任务的工期，将原图转换为下图，再使用关键路径法来求解?

对于特定网络图(所有路径的任务数都相同，比如本题，所有路径的任务数都是3个)，这种做法是可以的，比如上图：关键路径是甲→乙1→丙1→丁，距离为3*32—6—14—2=96—22=74公里。
但对于普通的网络图(所有路径的任务数不相同)，，这种转换方法则不成立。

转载请注明原文地址:https://kaotiyun.com/show/MvFZ777K

信息系统项目管理师上午综合知识考试

相关试题推荐

随机试题

最新回复(0)