已知网络图各段路线所需费用如下图所示，图中甲线和乙线上的数字分别代表相应点的有关费用。从甲线到乙线的最小费用路线有(1)条，最小费用为(2)。 (2)

admin2018-10-14 75

问题已知网络图各段路线所需费用如下图所示，图中甲线和乙线上的数字分别代表相应点的有关费用。从甲线到乙线的最小费用路线有(1)条，最小费用为(2)。

(2)

选项 A、15
B、16
C、17
D、18

答案C

解析这题考的是最短路径问题。
老套路，合并简化(利用Dijkstra最短路径算法的思想：最短路径的任意一段都是局部最优的)，将原图简化如下：

仍无法目测得出最短路径，继续进行简化：

此时，最小费用路线跃然而出，如下图所示，共有两条(下图中加粗显示)，最小费用为17。

原图中的最小费用路线如下(下图中加粗显示)。

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

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

相关试题推荐

随机试题

最新回复(0)