2. 从业资格
  3. 下图中，从①到⑧的最短路径有（ ）条。 A.1 B.2 C.3 D.4

下图中，从①到⑧的最短路径有（ ）条。 A.1 B.2 C.3 D.4

题库2022-08-02  13
问题 下图中，从①到⑧的最短路径有（  ）条。A.1B.2C.3D.4
选项 A.1
B.2
C.3
D.4
答案 B
解析 本考题考查的知识点为动态规划中的求最短路径。
原理：分阶段求最小解，从终点向起点推，用标注法。
（1）5-8的最短为12；6-8的最短为10；7-8的最短为14；
（2）2-5与2-6的最短为9，即2-8的最短为19（2-6-8）；同理3-8的最短为17（有两条：3-6-8；3-7-6-8；）；4-8的最短为19；
（3）1-2的最短为6，则经由2的1-8的最短为6+19=25；同理1-3的最短为4，则经由3的1-8的最短为4+17=21（有两条：1-3-6-8；1-3-7-6-8）；1-4的最短为5，则经由4的1-8的最短为5+19=24；
从而可判断：1-8的最短为21。有两条路径：1-3-6-8；1-3-7-6-8。
转载请注明原文地址:https://tihaiku.com/congyezige/2297198.html
本试题收录于： 高级信息系统项目管理师题库软件水平考试初中高级分类

高级信息系统项目管理师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)