下图中，从①到⑧的最短路径有 （ ） 条。
- 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。
包含此试题的试卷
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案