一、最短路径问题的概念和形式
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。
小编推荐
下载文档