下图中，从①到⑧的最短路径有 （ ） 条。
- 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。
