基于代码优化的最短路径算法.docx

基于代码优化的最短路径算法 目前，国内外对最短路径和改进算法的研究很多。最短路径算法主要包括dijksta算法、floyd算法、a-mans算法、worm算法和交替算法。dijksta算法和floyd算法相互关联，优化时间和空间复杂度，提高算法效率。时间和空间复杂度是评估算法质量的重要指标。因此，floyd算法的复杂交通网络稀疏部分与dijfstra算法的复杂交通网络密集部分相结合，以提高最短路径算法的研究。 1 学习方法 1.1 简化铁路运输路线 从中国铁路交通运输图中提取兰州—北京铁路交通网凸多边,在ARCGIS9.3软件下矢量化提取铁路交通运输路线图,得到简化后的交通运输路线(如图1所示). 1.2 传统floyd最短路径算法的实现 在实际应用中,当网络节点数较多时,传统的Floyd算法计算稀疏网络,效率低、空间复杂度高(O(N3)),而传统的Dijkstra算法计算稀疏图时,效率比Floyd算法高、时间复杂度为O(N2))且其代码的实现存在大量的∞无效运算,其研究思路如图2所示.因此我们主要从两方面实现传统Floyd最短路径算法的优化. (1)用Floyd算法计算稠密环网最短路径,用Dijkstra算法计算稀疏网最短路径,最后将两算法的结果合并的方法实现传统Floyd计算最短路径算法的优化,以便降低算法的时间、空间复杂性; (2)由于传统的Floyd算法的实现代码存在大量∞无效运算,因此考虑在算法的实现代码中加入判断语句的方法减少大量无效的∞运算,降低运算的时间复杂度及所占内存空间,如图2所示. 2 领域研究的应用 最短路径分析是GIS网络分析及其他研究领域研究的重点对象之一,并得到了广泛的应用;而Floyd算法与Dijkstra算法是国内外最短路径研究的经典算法. 2.1 算法1:将所有点标记的点c (1)传统Dijkstra算法传统的Dijkstra算法本身是一种贪婪算法,适于求单源、无负权的最短路径,稀疏图效果较佳、时间复杂度低(O(N2)).设每个点都有一对标号(dj,Pj),其中dj是从始点S到点j的最短路径的长度;Pj是从S到j的最短路径中j点的前一点.求解从起点S到点j的最短路径算法的基本思想: (1)初始化.起始点设置为:ds=0,Ps为空;所有其他点:di=∞,Pi=?;标记起始点S,记k=s,其他点均设为未标记的; (2)检验从所有已标记的点k到其直接连接的未标记的点j的距离,并设di=min[di,dk+1kj],其中1kj是从点k到j的直接连接距离; (3)选取下一个点.从所有未标记的节点中,选取di中最小的一个i:di=min[di],点i就被选为最短路径中的一点,并设为已标记的; (4)找到点i的前一点.从已标记的点中找到直接连接到点i的点j*,作为前一点,设置i=j*; (5)标记点i.如果所有点已标记,则算法完全推出,否则,记k=I,转到(2)再继续. (2)传统Floyd算法传统Floyd算法适用于APSP,是一种动态规划算法,稠密图效果最佳,边权可正可负.不适合站点数较多的情况.Floyd最短路径算法的基本思想: 在图的带权领接矩阵中用插入顶点的方法依次构造出V个矩阵D(1)、D(2)…、D(V),使最后得到的矩阵D(V)成为图的距离矩阵,同时也求出插入点矩阵以便得到两点间的最短路径.把带权领接矩阵W作为距离矩阵的初值,即D(0)=(Dij(0))VxV=W. (1)D(1)=(Dij(1))VxV,其中dij(1)=min{dij(1),di1(0)+d1j(0)};dij(1)是从Vi到Vj的只允许以V1作为中间点的路径中最短路的长度; (2)D(2)=(Dij(2))VxV,其中dij(1)=min{dij(2),di2(0)+d2j(0)};dij(2)是从Vi到Vj的只允许以V1、V2作为中间点的路径中最短路的长度. 2.2 floyd算法实现 (1)Floyd与Dijkstra结合的优化思想当网络节点较多时,Dijkstra和Floyd两种算法单独操作计算速度慢、占用内存空间大,尽管基于Floyd计算环路效率要高于Dijkstra算法,但时间复杂度为O(N3);而传统Dijkstra计算稀疏图的效率高特性,时间复杂度为O(N2).因此,采用Dijkstra算法与Floyd算法相结合的方法求复杂交通网络的最短路径比单一使用传统的Floyd或Dijkstra算法效率更高. (2)Floyd算法代码优化由传统的Floyd算法的实现代码可知,其核心算法为 求最短路径时存在大量无效MAX运算,耗时占运算的大部分时间,并且在程序设计中,判断语句所花费的时间可以忽略,并未增大计算量.因此,考虑在传统的Floyd实现代码中,在利用D[i][j]=min{(A[i][k]+A[k][j]