城市立体交通网络求最短路径的Dijkstra算法求解及其优化(3)

菜单

论文的具体结构如下：

第一章绪论。主要阐述了城市立体交通的典型问题，介绍了最短路径问题的研究意义，对当前典型的Dijkstra算法的研究现状和意义进行了阐述，并根据已知情况提出了相关研究的焦点问题。

第二章最短路径问题分析。对最短路径问题的分类和特点进行了较完善总结归纳，并分析研究了用于最短路径的三种搜索方案，详细介绍了Dijkstra算法的原理。

第三章城市立体交通对Dijkstra算法求最短路径的优化。阐述了优化了的Dijkstra算法，包括它的概念、特征、开发方法等；简单列举了南京市某区地图的节点图，验证优化了的Dijkstra算法在求多节点情况下的优越性，分段验证了双向Dijkstra算法的正确性，并给出最终结果。文献综述

第四章总结与展望。总结与展望。总结论文所做的工作，分析了其中算法的不足，并提出下一阶段研究的方向和所需要研究的对象。

2 最短路径问题分析

2．1最短路径问题的分类和特点[19]

最短路径根据划分的依据不同，其分类也不同。主要有三种划分依据：

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

第二，以度量为划分标准，可以将最短路径问题分为最短距离，最快路径和最短时间。产生这种分类的原因就是对“短”的主要想法不同，而侧重去着重于路径总权值，则是最短路径问题；侧重着重于行进的速度，则是最快路径问题；侧重着重于行进时间的花费，则是最短时间问题。

第三，以结点及路径数目为划分标准，我们把最短路径问题分为单对节点之间的最短路径问题，所有结点之间的最短路径问题，k则最短路径问题，有关出行时间的时间最短路径问题和特定必然经过的结点的最短路径问题。Nemhauser和Wolsey在1988年对最短路径的性质做了比较完全的研究讨论，得到最短路径必须具备的两个基本特点：

第一、从起点到终点的最短路径一定是由该路径上的各个子结点间最短路径组合而成的。综上所述，如果从结点A到结点B的最短路径中包含了结点C，那么结点B到结点C的子路径应该是所有从B到C的路径中最短的，该结果也同样适用于结点C到结点B的路径。由已知得，找到结点A到结点B之间的最短路径之前，必须找到组成的子最短路径的类似结点C的中间结点，因此必须通过分段来解出答案，然后逐步接近终点，以便最终获得整体最短路径的解答。

第二、一般情况下两节点的最短路径问题不能单单根据选择权重较小的成分弧段得出。就是说符合要求的问题的解将是所有弧段加起来总权值最小的那个解，仅仅根据由权重最小的部分弧段组合得到的最后结果将不是总权值最小的可能。源.自/751·论\文'网·www.751com.cn/

2．2最短路径的搜索策略：

搜索，即为求解两结点最短路径的最基本的方法。一般使用三种搜索策略：深度优先、广度优先和启发式搜索策略三种[21]。

2．2．1深度优先搜索：

在使用深度优先搜索策略时，所有结点之前都会被标记为未被访问过的，其次从结点B出发，与此同时把结点B标记为已访问的结点，然后从结点B出发去访问与A结点较接近的结点形，如果此结点形是新结点，那么这个结点形用B结点代替并成为新的出发结点，这样持续下去，直到所有与结点A可以相连的结点均被访问过。然后回到结点B的相邻结点继续以上步骤的搜索，直到所有的结点均被访问过而停止。这种搜索方法的时间复杂度为a(b“)，空间复杂度为A(bm)，其中分支系数用b表示，图的最大深度用m表示。