2最短路径问题分析

2.1最短路径问题的分类和特点

最短路径按照划分的依据不同，分类也不同。主要有三种划分依据:

第一，以空间维数为划分标准，可以将最短路径问题分为二维网络分析问题和三维空间曲面距离计算问题。最短路径不仅存在于二维平面上，在三维空间曲面上依然有最短路径问题。例如丘陵地形上的路径探索，仅仅依靠两点间的直线距离是得不到合理的结果的。具体的求解方式这里就不赘述了。

第二，以度量为划分标准，可以将最短路径问题分为最短距离，最快路径和最短时间。产生这种分类的原因就是对“短”的理解不同，侧重考虑路径总权值，则是最短路径问题；侧重考虑行进的速度，则是最快路径问题；侧重考虑行进时间的花费，则是最短时间问题。来~自^751论+文.网www.751com.cn/

第三，以结点及路径数目为划分标准，可以将最短路径问题分为单对节点间最短路径问题，所有结点问最短路径问题，ｋ则最短路径问题，出行时间有关的时间最短路径问题以及指定必经结点的最短路径问题[8]。

Nemhauser和Wolsey在1988年对最短路径的性质做了详细的讨论研究，得到最短路径应具备的两个基本特征：

第一、从起点到终点的最短路径一定是由路径上子结点间最短路径组成的。这句话的意思就是，如果从结点O到结点D的最短路径中包含结点K，那么结点D到结点K的子路径应该是所有从D到K的路径中最短的，结论同样适用于结点K到结点D的路径。如此看来，找到结点O到结点D之间的最短路径之前，必须找到类似结点Ｋ的中间结点所组成的子最短路径，因此需要通过分段求解，逐渐靠近终点，才能最终获得整体最短路径解。

第二、一般情况下最短路径不能单单依靠选择权重最小的部分弧段得出。就是说符合问题的解要求所有弧段加起来总权值最小，仅仅依靠权重最小的部分弧段组合得到的最后结果可能不是总权值最小的[9]。