最短路径算法英文文献翻译.doc

迪克斯特林算法的改进及在路线规划中的应用摘要：为了提高路网路线规划的效率，许多专家学者对此进行了一些研究。Dijk stra算法是一个研究热点。在两点之间寻找一个最佳路径时迪克斯特拉算法也有自己的缺点，但它仍具有无可替代的优势。通过对经典Dijk stra算法优势和劣势的分析，我们可以发现，主要缺点可以概括为两点：存储结构和搜索区域。因此，本文改进了这两点，即数据存储结构和限制算法搜索区域的改进。通过分析实验结果获得其有效性。关键词：迪克斯特拉算法；道路网络；路线规划；存储结构；受限搜索区域 引言基于拓扑结构的道路网络，路线规划是为车辆运行期间到达目的地而进行的一种搜索最佳路径的过程以及车辆导航系统中最短路径问题的一种具体应用。迪克斯特拉算法是在图中搜索最短路径最经典最成熟的算法，然而，该算法具有较高的时间复杂度以及要占有较大的存储空间。为了克服迪克斯特拉算法的这些缺点，专家学者也相应做了大量的研究，他们的研究成果有各自的特点和优点，但相关算法的理论基础是迪克斯特拉算法，结合实际交通网络的分布特性，此论文改进了经典的迪克斯特拉算法以减少时间复杂度和存储空间，和减少算法的搜索规模，以此提高算法的运行效率。 存储结构A 存储结构的改进运用图片说明存储结构的改进原则，如图片1所示，采用邻接矩阵存储迪克斯特拉算法的数据，图片2显示各节点之间拓扑关系的邻接矩阵的结构，采用一个1010的矩阵来存储点与点之间的拓扑关系，行与列同等数目。矩阵xi,xj的值对应于节点i和j之间的权值，当源节点和末节点是同一个节点时，权值为0，两节点之间无直接路径时权值为。此矩阵含有大量的0和，这也增加了无效路径的数目并占有了存储的大量空间。因此从时间和空间的角度来看是不科学的。 3 0 2 3 4 3 2 0 4 3 2 42 4 0 3 9 2 3 3 0 5 2 3 2 5 5 0 4 3 5 2 4 0 3 51 2 3 0 4 1 10 3 3 4 0 4 2 3 0 586 1 1 5 07 3 3 图片1，拓扑结构 图片2，邻接矩阵 关于上面提到存储模式，通过减少不必要的0和来压缩数据存储空间，用邻接表来存储数据。（1）用表数组MGraph来表示存储矩阵G，邻接矩阵的每一行用单一的连接列表来表示，链接表中只存储非元素。每个节点有两个元素，一个是列值，另一个是权值。图3表示图1的存储方式： 8 3 G12 2 9 2 8 33 41 2G2 4 3 2 4G3 9 3 6 45 53 3G4 6 4 4 5G55 4 4 2G610 1 8 46 3G7 9 5 10 5 7 4 4 37 12 22 31 3G10G9G8（2）每个点到源点的最短距离存储在一维数组D中。（3）前一个节点存储在一维数组P中。（4）参与比较的节点存储在一个辅助的双向链表中。算法步骤如下： 步骤1，和节点v0直接相连的节点的D（vi）将被初始化为其权值，其余的为计算机所允许的最大值。 步骤2，和v0直接相连的节点被添加到路径列表中。 步骤3，找出具有最小权值的节点w，并在路线中删除w，如果剩余节点是0，就结束。 步骤4，修改最短路径，图G中和节点w直接相连的其他节点之间比较Dvi和D（w）+s(w,vi)，如果Dvi的值比D（w）+s(w,vi)的值小或者Dvi的值为，把vi加入到路径中。P(vi)的前一个节点设置为w,最短路径被修改为P(vi)= D（w）+s(w,vi)。然后重复步骤2。B 复杂度分析 （1）空间复杂度的分析因为采用列表数组MGraph，其空间复杂度是O(T)，T是图的边的数目。在最糟糕的情况下，如果T=n2,那么空间复杂度就为O(n2)。 （2）时间复杂度的分析存储结构改进后，实施算法四步骤的时间复杂度如下：步骤1的时间复杂度为O(n)；步骤2的时间复杂度为O(n)；对于步骤3，第一循环的数目就是和v0直接相连的节点数目，即n1。和首次发现的且和v0的距离为的节点直接相连的节点数目加上n1-1即可得到第二循环的数目。直到节点数目为0即可得出分析结论，然后结束。最糟糕的情况是，节点v0和每个节点都有联系，其循环数目相应的就是（n-1）,（n-2）,1，相应的时间复杂度就是（n-1）+（n-2）+1，即O(n2)。步骤4的时间复杂度是O(T)，在最糟糕的情况下，如果T=n2,那么空间复杂度就为O(n2)。因此，存储结构改进后的算法的时间复杂度是maxO(n),O(T),O(n2),即O(n2)，时间复杂度是古典的迪克斯特拉算法相同。但是都市路线网络的节点比较多，而且路线网络所对应的有向图是不完整的，节点的度小于5个，所以Tn2，在这种情况下，改进后的存储结构非常实用而且有效，消除了存储冗余的冗余计算。 搜索区域A 受限的搜索区域 因为经典的迪克斯特拉算法是一种全面的搜索过程，所以是肯定有冗余的，根据迪克斯特拉算法的特点以及实际道路网络的空间分布特征，算法必然会限制搜索区域，因为两点之间直线距离是最短的，当我们规划实际道路网络的时候，起始节点与终止节点之间通常是无法直达的，即两点之间最终实际的最短路径通常是两侧的连接线，一般都在其附近。如果两点之间仅仅只有一条边，此边本身就是最短路径，然而，有时两点附近可能存在距离较短的其他路径，也就是说，为了进入右行车道，车辆会行驶在此路线。C圆形区域 P黑色粗线环绕的区域 S起始节点 D终止节点 RS到D的欧氏距离 R1小矩形 R2大矩形 T1阈值（从L1，L2到D） T2阈值（两个阈值之间的距离） 图片4 经典的dijkstra算法的比较示意图及受限搜索区域算法图片4显示，为了寻找从起始节点S到终止节点D的最短路径，一个dijkstra算法理论搜索区域是一个圆形区域C，圆心是S，半径是R。受限搜索区域算法的理论搜索区域是边界R1，对角线是S到D的那条线（当S到D的那条线是水平或垂直的时候，就有一个直线片段）。同时，考虑到有其他路径，R1的每一边都可以延伸到T2边界之外，以此形成一个大的矩形R2，L1和L2形成受限的搜索区域以切割矩形R2，L1和L2是平行于直线片段SD的两条直线，距离是T1，如图4所示，搜索区域P是由封闭的粗线组成。B 搜索区域分析（1）经典的dijkstra算法的搜索区域是A1=R2；（2）受限搜索区域算法的搜索区域是A22T1R+T2（3）因为搜索节点和搜索区域是匹配的，相应的它们的时间复杂度是O(A12)和O(A22)。通常T1，T2相应的是较小的常数，因此，时间复杂度的比例大约可以表示为O(A12)/O(A22) A12 /A22R4/R2=R2。通过比较，我们可以发现受限搜索区域算法的搜索区域比古典dijkstra算法的搜索区域要小。随着道路网络规模的增大以及邻近节点距离的加大，时间复杂度的差异将更加明显，因此，必定限制搜索区域的算法经改进后，将减少算法搜索的规模，减小其复杂度，提高系统的效率。 应用实例和结果分析为了比较两种算法的优势和劣势，VC+实现了带有3600节点的随机公路网络（CPU:2.0； main memory:512M； OS:WINXP） 古典dijkstra算法搜索区域的示意图改进后的算法搜索区域的示意图此论文只给出了一个搜索结果，从起始节点1974到目标节点2689。古典dijkstra算法的搜索结果在图片5中给出，待搜索节点的数目是627；改进后的搜索结果在图片6中给出，待搜索的节点数目是243。黑色线条是相关算法的最短路径，通过比较，我们可以发现最短路径是相同的，但是古典dijkstra算法的搜索区域非常接近于一个圆形区域，而改进后的算法的搜索区域更接近于一个矩形。下表中给出了8组实验数据，t1表示古典dijkstra算法的搜索时间；t2表示改进后的算法的搜索时间；n1表示古典dijkstra算法搜索的节点数目；n2表示改进后的算法搜索的节点的数目。 Dijkstra 改进后起始 目标 算法 的算法 t2/t1 n2/n1 (%) (%)节点 节点 t1(s) n1 t2(s) n21974 2689 2.365 627 0.156 243 6.60 38.60 33 675 1.433 486 0.092 183 6.40 37.70 689 1980 2.895 974 0.214 352 7.10 36.101632 3520 4.198 1395 0.293 517 7.00 37.101938 3211 2.877 955 0.212 339 7.40 35.501222 3333 3.985 1541 0.277 578 7.00 37.50769 2813 4.061 1480 0.337 562 8.30 38.101137 2928 3.846 1228 0.279 484 7.70 39.40 两种算法的搜索结果从上表中的数据我们可以看出，被改进后的算法搜索的节点的数目大约是古典dijkstra算法节点数目的1/3。改进后的算法的搜索时间大约是古典dijkstra算法的1/10。因此，我们可以得出一个结论，实时路径规划明显增强了。不幸的是，改进后的算法本身限制了搜索区域，可能算法有时候不能搜索真正的最短路径，只是一个相对较短的路径，这是一个有缺陷的最短路径算法，优化时降低了其精确度。但是在很多情况下，最短路径是在矩形内的，整体来说，优化算法的优势是显而易见的，改进后的算法到达了优化的目的。 结论此论文基于城市交通网络空间分布特征并且结合古典dijkstra算法本身的特点，降低了算法的搜索规模，提高了运行效率，结果显示，算法的改进是合理的有效的。参考文献：1 赵译林 车辆定位与导航系统 北京电子工业出版社 19992 陆峰 最短路径算法：分类和进展研究 20013 福蒙阴 李继 邓志宏 限制搜索区域的分层路由规划算法 计算机辅助设计与图形学杂志 20054