最短路径问题的概念和形式

一、最短路径问题的概念和形式

1、最短路径问题

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

2、最短路径问题的形式

（1）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

（2）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于将问题变为反向来确定起点的问题。

（3）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

二、最短路径问题的相关例题

一只蚂蚁从圆柱体的下底面$A$点（左下角）沿着侧面爬到上底面$B$点（右上角），已知圆柱的底面半径为2cm，高为8cm（π取3），则蚂蚁所走过的最短路径是___

A．8 B．9 C．10 D．12

答案：C

解析：把圆柱侧面展开，点$A$、$B$的最短距离为线段$AB$的长。在Rt$△ABC$中，$∠ACB=90°$，$BC$=8cm，$AC$为底面半圆弧长，$AC$=2π=6cm，所以$AB =\sqrt{AC^2+BC^2}$=10cm。故选C。

小编推荐

1.12个月份的英语缩写形式

2.曹衣出水形容哪种艺术形式 影响有哪些

3.中国历史上最短的朝代 是谁建立的

4.学生会15个经典面试问题 怎么回答更吸睛

5.学生会面试的30个问题及答案整理

6.地球上最早的生命形式是什么

7.学生面试必问10大问题回答 有什么技巧

8.考上空军航空大学是什么概念 很厉害吗