基于Dijkstra的最短路径算法的优化及应用

《基于Dijkstra的最短路径算法的优化及应用》由会员分享，可在线阅读，更多相关《基于Dijkstra的最短路径算法的优化及应用（35页珍藏版）》请在装配图网上搜索。

1、本科学生毕业论文论文题目：基于Dijkstra的最短路径算法的优化及应用学 院：年 级：专 业：姓 名：学 号：指导教师：2011年5月20日摘要随着计算机和地理信息科学的发展，GIS（地理信息系统）的应用领域越来越广。最短路径分析是GIS地理网络分析功能中的一个关键性的问题。计算最短路径的经典算法之一就是Dijkstra算法，许多工程中解决最短路径问题都是采用这种算法。然而，传统的Dijkstra算法在求解节点间最短路径时，对已标识节点外的大量节点进行了计算，从而影响了算法的速度。本文在传统Dijkstra算法的基础上，对其进行了优化，此优化算法只对最短路径上节点的邻居做了一些处理，从而不涉

2、及到其他的一些节点。故而，此优化算法在计算的节点数较传统算法大幅减少，提高了算法的速度。本文通过实验和实际应用对改进后的算法进行了简单的验证。关键词最短路径；Dijkstra；优化算法AbstractWith the development of computer and geographic information science,the applications of GIS (Geographic Information System) are becoming more and more widely.However, shortest path analysis is the key

3、 problem of network analyses,Dijkstra algorithm is a classic arithmetic for the shortest path.It is the academic foundation that many engineerings were solved in the shortest path is use.When a shortest path between nodes is searched with Dijkstra algorithm,a lot of nodes away from lagged nodes are

4、involved,so that the efficiency of Dijkstra algorithm is low.An optimization algorithm is presented in this paper based on analysis of Dijkstra algorithm.Only these nodes that the neighbor of nodes in the shortest path are processed,and other nodes are not processed.Therefore,the number of processed

5、 nodes is largely reduced in the optimization algorithm,and efficiency of the optimization algorithm is improved.The improved algorithm is proved to be correct and efficient by experiments and practical application.Key wordsthe shortest path；Dijkstra；optimizationalgorithmII目录摘要IAbstractII第一章 绪论1一、国内

6、外最短路径算法的发展及其概况1二、传统Dijkstra算法仍然存在的一些问题1三、本文研究的内容及意义2第二章 Dijkstra经典算法3一、原理及应用3（一）原理3（二）应用4（三）优缺点7二、Dijkstra算法与其他主流算法的比较9（一）搜索速度比较9（二）搜索成功率比较10第三章 基于Dijkstra算法的优化算法的研究12一、几种优化算法12（一）减小算法中成功搜索的搜索范围12（二）改进算法的存储结构12二、本文对Dijlstra优化算法研究12（一）目标13（二）思路13（三）描述14（四）特点17三、本文优化算法与传统算法的比较18第四章 此优化算法在消防中的相关应用19一、消

7、防力量调集路径最优指标的选取19二、Dijkstra最短路径经典算法及分析20（一）问题定义20（二）Dijkstra算法20（三）Dijkstra算法优化及分析201优化Dijkstra算法的思路202优化Dijkstra算法的描述21结论22参考文献23附录一24致谢31第一章 绪论一、国内外最短路径算法的发展及其概况最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多科学家在研究。但给出求解的基本思想的人直到1959年才出现，是一位名叫Edsger Wybe Dijkstra (迪杰斯特拉)的荷兰计算机科学家，他不仅给出了求解的基本思想，还给出了算法。他给出的算法主要解决

8、的问题是从某一个固定的点到其他各点的最短路径问题。后来这个算法被誉为一代经典，被称作Dijkstra算法。后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定情况下。确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法1。而不确定情况下对最短问题的研究又分成了四个方面：研究路段长度随机变化的最短路径问题，以Frank和Mirchandani为代表；研究不同费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下的路段长

9、度随机变化的最短路径问题，Hall、LiPing Fu、L.R.Rilett、Elise和Hani为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表。其中，第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题”。二、传统Dijkstra算法仍然存在的一些问题 原始Dijkstra算法在存储图形数据和运算时，基于网络的权矩阵，需要根据其节点与距离之间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义NN的数组来存储数据，其中N为网络的节点数，当网络的节点数较大时，将占用大量的计算机内存。 原始Dijkstra算法在运行时

10、一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型。网络中所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法。根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率。三、本文研究的内容及意义随着社会的不断进步，最短路径算法在人们的日常生活显得越来越重要。每天开车去上班，应该选择哪条公路才能使自己到公司的费用最低、时间最少，这是最短路径的问题；在网络路由中，怎样选择最优的路由路径

11、，这也是最短路径问题；在交通旅游、城市规划以及电网架设中怎样使其耗费的资金最少，这还是最短路径问题。由此可见对最短路径问题的研究是非常有意义的。最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很多种，其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划等领域都应用广泛。第二章 Dijkstra经典算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它

12、遍历计算的节点很多，所以效率低2。一、原理及应用 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。（一）原理Dijkstra算法是1959年由EWDijkstra提出的图论中求最短路径的一个著名

13、的算法，使用其可以求得图中一点到其他各顶点的最短路径。原始的Dijkstra算法将网络结点分成3部分：未标记结点、临时标记结点和永久标记结点。网络中所有结点首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结点来结束算法。假设每个点都有一对标号 (wj, pj)，其中wj 是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj 则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算

14、法的基本过程如下：1)初始化。起源点设置为： ws=0, ps为空； 所有其他点: wi=, pi=?；标记起源点s，记k=s,其他所有点设为未标记的。2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：wj=minwj, wk+dkj 式中，dkj 是从点k到j的直接连接距离。3)选取下一个点。从所有未标记的结点中，选取wj中最小的一个i:wi=min wj，（所有未标记的点j），点i就被选为最短路径中的一点，并设为已标记的。4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，设置：i=j*。5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=

15、i，转到2)再继续。 0 100 10 41 30 10 50 6032 20 图 2-1 Dijkstra算法最短路径应用演示图表 2-1 从0节点到4节点的最短路径循环红点集SKD0D1D2D3D4P0P1P2P3P4初始化001030100-10-10010,110106030100-1010020,1,33010503090-1030330,1,3,22010503060-1030240,1,3,2,44010503060-10302（二）应用给定简单无向图G,指定一顶点Vi为起点,对于任意 VjG 且ij,求Vi到Vj 的最短路径的长度。例:北京的小汤山医院已经投入使用了,在抗击非典

16、的战役中发挥了重要的作用。现在,在北京市内有若干家收治非典病人的医院。各个医院之间的路程和各医院到小汤山之间的路程已知(有可能没有直通道路),由于非典病人的特殊性,在往小汤山转运的过程中只能在收治病人的医院中转。现在,党和政府交给了你一个光荣而艰巨的任务,计算出小汤山到市内各收治医院的最短路径,为抗非事业做出你应有的贡献。给定问题的算法分析:1)初始化：起点的最短路径为0，其他顶点的最短路径为，所有顶点未标号。2)在所有未标号的顶点中找出最短路径最短的顶点i。若无法找到，则说明所有顶点已标号，或者所有的未标号顶点都是无法到达的，转5)。3)更改所有与i直接相邻的未标号顶点的最短路径。更新方法如

17、下：如果i的最短路径边ij 的长度距离2,所以不更新)医院1已标号距离0医院2未标号距离12医院3已标号距离4医院4以标号距离912456图 2-5 小汤山医院位置图找所有未标号中距离最短的顶点为医院2,将2做标号,已没有与2相邻的未标号顶点需要更新了医院1已标号距离0医院2已标号距离医院3已标号距离4医院4已标号距离912456图 2-6 小汤山医院位置图再次找所有未标号中距离最短的顶点已找不到,得结果d(2)=12,d(3)=4,d(4)=9.（三）优缺点Dijkstra算法能够保证100%找到最优解，但其搜索速度较慢，搜索效率非常低，时间花费较多，一般只能用于离线的路径规划问题。如节点数

18、为n的图，用Dijkstra算法计算最短路径总共需要迭代n一1次，每次迭代都新加一个节点到临时节点集合中，由于第i次迭代时不在临时节点集合中的节点数为n-i即第i次迭代需对n-i个节点进行处理，因此其所需的处理数为，对n个节点网络的时间复杂度是O(n2)。在实际应用当中，使用Dijkstra算法查找最短路径时耗费大量的时间进行数据的比较，本文对Dijkstra算法进行分析，通过改变算法实现减少不必要节点计算的时间，提高算法的效率达到对其进行优化。下一个例子说明Dijkstra算法存在的缺陷：例：图2-7所示为一带权图G(V，E，W)，求从v1出发到其它各个顶点的最短路径长度。图 2-7 权图G

19、解：wi表示由源v1到点vi的最短距离；S表示已求出最短路径的顶点集合，其初始值为Sv1；k表示刚选出的顶点的编号；选出vk后修改U中各顶点的距离的方法为：wi=minwi，dki；表 2-2 Dijkstra算法来求解图2-7的最短路径长度-初始第一步第二步第三步-v1159-v2-v34-v4-v510-v6-S=v1-v4v2-k-w-S-v1,v4v1,v2,v4-在上表中选出顶点v4加入到S时一共进行了6次比较，其中四次是与作比较，也就是说这四次完全没有必要进行比较。当选出v4后，需要对U中的各个顶点的距离进行调整，在调整过程中利用到wi =minwi,w4+d4i其中i1，4(1，

20、4已经在S中)即需要对wi和w4+d4i进行比较，但我们在对w3,w5,w7进行调整时可以发现由于d43,d45,d47 E(G)即它们的权值为，所以调整时是没有必要进行比较的，在这里多进行了3次比较。后面的各步也都出现类似的情况(后略)，尤其是当图的边数相对较少时更为明显。二、Dijkstra算法与其他主流算法的比较（一）搜索速度比较对5张图分别采用Dijkstra算法、A*算法3、遗传算法4进行路径规划，他们各自花费的时间如表2-3所示。表 2-3 三种算法在搜索速度上的对比节点数搜索速度DijkstraA*算法 遗传算法1611232424437366215597825712 由表2-3

21、可以看出：当地图节点个数和弧的条数比较少时，三种算法所花费的时间差不多，当节点个数和弧的条数比较多时，A*算法最快，遗传算法其次，Dijkstra算法最慢，而且这种差距将随节点和弧数量的增加而变得更加明显。对于实际地图而言，由于节点与道路的数量一般都很的大，Dijkstra算法在搜索速度方面弱势明显。（二）搜索成功率比较对于具有n个节点的地图，其待规划节点的个数为n-1（除起点节点外，其他均可作为待规划节点），由于每个待规划节点对应于一条最短路径，所以对每张具有n个节点的地图而言，应该规划出n-1条最短路径。对5张地图分别采用三种算法进行路径规划，三者各自搜索到最短路径的情况如表2-4所示。表

22、中括号外数据为各算法实际得到最短路径数，括号内数据则为各算法实际得到路径数和应该规划出的最短路径数n-1之比5。表 2-4 三种算法在搜索质量方面的对比节点数 Dijkstra A*算法 遗传算法 16 15(100%) 12(80%) 15(100%)32 31(100%) 25(81%) 29(94%)43 42(100%) 32(76%) 38(90%)62 61(100%) 40(66%) 56(92%)78 77(100%) 45(58%) 71(92%)由表2-4可以看出：当地图节点个数和弧数量比较多时，Dijkstra算法是一种遍历算法，每次能保证100%搜索到最短路径，遗传算法

23、搜索到最短路径的成功率比Dijkstra算法低一些，A*算法最低，且这种差距在节点数和弧数量越大时更加明显。第三章 基于Dijkstra算法的优化算法的研究一、几种优化算法（一）减小算法中成功搜索的搜索范围减小算法中成功搜索的搜索范围以尽快到达目标节点。在对现实问题中的交通图初始化为网络拓扑图时，虽然终点已知，而源点尚未确定，但依据常识离案发地段最近的派出所应为案发地段所在辖区派出所，或其周边派出所，也就是源点的选取范围可以确定。利用MapObjects2组件提供的MapLayer.SearchExpression (expression)记录集筛选方法，根据案发地段(终点)的不同，动态选取案

24、发地段所在辖区及相邻辖区的道路图层及派出所图层数据进行最短路径查询，从而有效地减少了拓扑图中节点总数n的值6。（二）改进算法的存储结构在实际工作中，还要建立起空间数据结构。网络数据结构使用的是“边和节点”的数据结构，该数据结构是建立在图论的基础上，节点可用来定义边的连接关系。对于网络数据的存储，传统的是采用图论中的邻接矩阵方法，其存储量为NN(N为网络中节点数)。通常的地理网络，尽管节点很多，但与节点相关联的节点数目并不多，一般都为稀疏图，将会浪费大量的空间。若采用邻接表的链式存储结构，其存储量为E(E为节点列表中，同节点关联的所有边的数目)，可节省大量的存储空间，尤其是在表示与节点和边相关信

25、息较多的地理网络时，更为有效。但邻接表却难以判断两节点之间的关系，因此本文提出利用。NET框架提供的特殊类Hashtable。NET框架包含特殊类，比如通常所说的集合类用于存储对象。与数组类似，集合类可以把对象放入容器中，然后再取出但集合的使用方法与数组不同，拥有用于插入和删除项的专用方法。使用Hashtable最大的优点就是大大降低数据存储和查找的时间花费，几乎可看成是常数时间。二、本文对Dijlstra优化算法研究本文采用第一类优化算法减小搜索范围的思路对Dijkstra算法进行优化。（一）目标Dijkstra算法用来求解图上从任一节点(源点)到其余各节点的最短路径。其时间复杂度为O(N2

26、)；采用邻接矩阵存储网络拓扑结构，需要(NN)的存储空间，随着节点数N的增大，其计算效率和存储效率越低。针对此问题，提出了Dijkstra算法的改进，本文在对传统Dijkstra算法分析的基础上，对其进行了优化，优化算法只对最短路径上节点的邻居做处理，而不涉及到其他节点7。（二）思路Dijkstra算法基本方法：设wj是从源点s到节点j的最短路径长度；pj是从s到j的最短路径中j点的前一节点。S是标识集合；T是未标识集合；M是节点集合。dij提节点i到节点j的距离(i与j直接相连，否则dij = )算法步骤如下：Step0：S = s；T = M-S；wj = dij(jT，s与j直接相连)或

27、wj = (j T，s与j不直接相连)。Step1：在T中找到节点i，使s到i的距离最小，并将i划归到S。(可从与s直接相连的j中考虑)若dsi = min dsj j与s直接相连，则将i划归到S中，即S =s，i，T = T-i；jTpi =s。Step2：修改T中j节点的wj值：wj = min(wj,wi + dij)；若wj值改变，则pj = i jTiSStep3：选定所有的wj最小值，并将其划归到S中：wi = min wj；S=Si；T=T-i；若S= n, 所有节点已标识，则算法终jT止，否则，转人Step2。通过分析传统Dijkstra算法的基本思路，传统Dijkstra算法

28、存在如下两点不足：(1)当从未标记节点集合T中选定一个节点k作为转接点后时，需扫描未标记节点集合T中的节点j并更新其wj值，而未标记节点集合T中往往包含大量与转接节点k 不直接相连的节点i(即dki =)；(2)在未标记节点集合T中选择一个w值最小的节点作为下一个转接节点，然而下一个转接节点往往是与标记节点集合S中的节点直接相连的。（三）描述基于上述两点不足，对传统Dijkstra算法进行优化，算法优化思路为：首先从源点s的邻居集合NBS(与s直接相连的节点集合)中选择距离最小的邻居节点k作为转接点，同时将划归到标识集合S(初始时，S为s)。然后对k邻居集合与标识集合的差集8(NBk S)中节

29、点的值进行更新，从标识集合s中所有节点的邻居集合的并集与标识集合的差集(NBsS，iS)中选择一个wk值最小的节点作为下一个转接点，并划归到标识集合S中。重复上述过程，直到所有的节点都被标识过，即S=n，算法结束。设NBi为节点i的邻居集合；S为标识集合；wj是从源点s到节点j的最短路径长度；pj是从s到j的最短路径中j点的前一节点；dij是节点i到节点j的距离。算法步骤如下：Step0：初始化S = s；wi = dsi(iNBs)；否则 = (I NBs)；pi=s。Step1：若dsk = min dsj ，则S = S k。 jNBsStep2：修改NBk - S中的wj值：wj =

30、min wj,wk +dkj ；若wj值改变，则 pj = k。jNBs -SStep3：选定NBi - S(iS)中的wj最小值，并将其划归到s中： wk = min wj；S = S k；若s= n；所有节点已标识，则算法终止， jNBsSiS否则，转到Step2图3-1为带权值的无向图G7，对G7分别用Dijkstra算法和优化了的Dijkstra算法进行求解，则可得从v1到其余各节点的最短路径9。图 3-1 非负权值图经典Dijkstra算法求解过程：Step0：初始化S = (v1)，w1 = 0，T = (v2,v4, v3,v5, v6,v7)；Step1：w4 = d14 =

31、mind1j = 2（d12 = d14，任选其一，本文选v4），S = (v1,v4)，jTT=(v2,v3,v5,v6,v7)；Step2：T= (v2,v3,v5,v6,v7)w2 = minw2,w4 + d42= min2,4= 2，w3 = minw3,w4 + d43= min5,5 = 5 2 = w2，w5 = minw5,w4 + d45 = ,3 = 3 2 = w2，w6 = minw6,w4 + d46 = ， (3-1)w7 = minw7,w4 + d47 = ， (3-2)minwj =w2 = 2，S = (v1,v2,v4)，T = (v3,v5,v6,v7

32、)；Step3：T = (v3,v5,v6,v7)w3 = minw3,w2 + d23 = min5,5 = 5，w5 = minw5,w2 + d25 = min3, = 3 5 = w3，w6 = minw6,w4 + d46 = ， (3-3)w7 = minw7,w4 + d47 = ， (3-4)minwj = w5 = 3，S = (v1,v2,v4,v5)，T = (v3,v6,v7)；Step4：T = (v3,v6,v7)w3 = minw3,w5 + d53 = min5,4 = 4，w6 = minw6,w5 + d56 = ,4 = 4 = w3，w7 = minw7

33、,w5 + d57 = ,5 = 5 4 = w3 = w6，minwj = w3 = w6 = 4，任选其一，若为w3，S = (v1,v2,v3,v4,v5)，T = (v6,v7)；Step5：T = (v6,v7)w6 = minw6,w3+d36= min4, = 4，w7 = minw7,w3 + d37 = 5, = 5 4 = w3 = w6，minwj = w6 = 4，S = (v1,v2,v3,v4,v5,v6)，T = (v7)；Step6：T = (v7)w7 = minw7,w6 + d67 = 5,6 = 5。至此，所有节点已标识，则算法终止。最终结果为w2 =

34、2，w3=4，w4=2，w5=3，w6=4，w7=5，w6=4，w7=5。优化Dijkstra算法求解过程：表 3-1 优化的Dijkstra算法求解v1到其他各节点最短路径的过程迭代代数V1V2V3V4V5V6V7选定点WiNBiSNBI-SNBI-S01252-V1W1=0(V2,V3,V4)(V1)-1-25-V4W4=2(V1,V2,V3,V5)(V1,V4)(V2,V3,V5)(V2,V3,V5)2-4-3-V2W2=2(V1,V3,V4)(V1,V2,V4)(V3)(V3,V5)3-4-V5W5=3(V3,V4,V6,V7)(V1,V2,V4,V5)(V3,V6,V7)(V3,V6

35、,V7)4-45V3W3=4(V1,V2,V4,V5,V6)(V,1V2,V3,V4,V5)(V6)(V6,V7)5-5V6W6=4(V3,V5,V7)(V1,V2,V3,V4,V5,V6,V7)(V7)(V7)6-V7W7=5(V5,V6)(V1,V2,V3,V4,V5,V6,V7)Step0：初始化S = (v1)，与v1直接相连的点有v2v3v4，NB1 = (v2,v3,v4)，w1 = 0；Step1：w4 = d14 = mind1j = 2（d12 = d14，任选其一，本文选v4），S = (v1,v4)，jNB1NB4=(v1,v2,v3,v5)，NB4 S = (v2,v3

36、,v5)，NB4-S = (v2,v3,v5)； Step2：jNB4 S = (v2,v3,v5)w2 = minw2,w4 + d42= min2,4= 2，w3 = minw3,w4 + d43= min5,5 = 5 2 = w2，w5 = minw5,w4 + d45 = ,3 = 3 2 = w2minwj =w2 = 2，S = (v1,v2,v4)，NB2 = (v1,v3,v4)，NB2-S = (v3)，NB2-S = (v3,v5)；Step3：jNB2-S = (v3,v5)w3 = minw3,w2 + d23 = min5,5 = 5，w5 = 3 5 = w3，m

37、inwj = w5 = 3，S = (v1,v2,v4,v5)，NB5 = (v3,v4,v6,v7)，NB5-S = (v3,v6,v7)，NB5-S = (v3,v6,v7)；Step4：jNB4 S = (v3,v6,v7)w3 = minw3,w5 + d53 = min5,4 = 4，w6 = minw6,w5 + d56 = ,4 = 4 = w3，w7 = minw7,w5 + d57 = ,5 = 5 4 = w3 = w6，minwj = w3 = w6 = 4，任选其一，若为w3，S = (v1,v2,v3,v4,v5)，NB3 = (v1,v2,v4,v5,v6)，NB3

38、-S = (v6)，NB3-S = (v6,v7)；Step5：jNB3-S = (v6,v7)w6 = 4w7 = 5 4 = w6，minwj = w6 = 4，S = (v1,v2,v3,v4,v5,v6)，NB6 = (v3,v5,v7)，NB6-S = (v7)，NB6-S = (v7)；Step6：jNB6 S = (v7)w7 = minw7,w6 + d67 = 5,6 = 5。至此，所有节点已标识，则算法终止。最终结果为w2 = 2，w3=4，w4=2，w5=3，w6=4，w7=5，w6=4，w7=5。（四）特点传统Dijkstra算法基于广度优先的搜索策略，从指定节点出发，

39、通过权值迭代遍历所有其他节点后，最后得到从指定节点到其他各节点的最短路径树。它采用线性数组结构存储其关联矩阵，在提取最短路径节点时需要访问所有的未标记节点，算法的运行时间为O(n2)10。本文提出的优化算法在更新最短路径值与选择最短路径值最小的节点时，仅仅涉及到节点的邻居集合及已标识集合中所有节点的邻居集合与已标识集合的差集，其运行时间取决于转接点的邻居集合的元素数量多少(而该数量值往往小于未标识集合中的元素个数)。优化算法空间复杂度为O(np)，其中P是常量，为结点对象所占用的空间。另外，根据图中顶点和边的个数，可以求出顶点的平均出度e=mn(m为边数，n为顶点数)，一般在GIS的网络图中，

40、e2，5，由于Step2、Step3都是搜索与Vi(i=l，2，3,，n)相邻的结点操作，时间复杂度均为O(Ne)；Step3的时间复杂度为O(m)，即O(ne)；步骤(5)的时间复杂度为O(ne)。因此，算法的时间复杂度为O(ne)。三、本文优化算法与传统算法的比较由3.2.3章节对带权值的无向图G7的求解可以看出，优化了的dijkstra算法在Step2和Step3中较经典的Dijkstra算法减少了步骤(3-1)(3-2)(3-3)(3-4)，减少了计算次数，提高了搜索速度。当网络拓扑结构图具有的节点数，v较大且其关联矩阵为一个稀疏矩阵时，相对传统Dijkstra算法，优化算法大大减少了

41、计算次数与比较次数，在一定程度上提高了运算速度。在分析传统Dijkstra算法的基础上，针对传统Dijkstra算法存在的两点不足之处，对其进行了优化处理。当网络的规模较大及其关联矩阵为一个稀疏矩阵时，本文提出的优化算法，与传统Dijkstra算法相比，能大大减少了计算次数及比较次数，提高了运算效率11。第四章 此优化算法在消防中的相关应用火灾是城市中较为频繁的灾害，其损失经常是巨大的。如果在火灾发生后的短暂时间内，消防力量能有效地控制火势，则火灾损失会大大减少。火灾的经济损失有很大的波动性，它与火灾的持续时间、燃烧物的类别、过火面积等因素有关。但是，对于一个具体的建筑物子系统，火灾损失的变化

42、主要与火灾持续时间有关。消防队必须在15分钟内达到火场出水，这是基于我国通讯、道路和消防装备的实际情况以及对大量的火灾案例的分析得出的，这样才能有效地扑救火灾并防止火势继续蔓延。但在实际工作中往往由于消防资源调度不当等各种迟滞因素使得消防人员不能尽早赶到火灾事故现场，丧失了对早期火灾扑救的良好时机。为将损失降低到最低程度，消防部门面临的问题是如何迅速调动消防救援力量到达事故地点及时扑灭火灾，这就涉及到调集路径选取的问题。地理信息系统中的Dijkstra最短路径算法可以很好的解决这个问题。一、消防力量调集路径最优指标的选取Dijkstra算法在通用路径选择算法中，对最短路径的衡量标准是通过计算路

43、径的边权来决定的。如何确定边权，使设定的边权更符合系统实际的需要，是建立算法参数标准的重要因素，其值设定的好坏，直接决定了算法的适用性。在实际城市交通网络中，道路长度最短的路径不一定是耗时最短的。如何设定最优路径的标准也是设计权值的重要前提。影响消防车辆到达火灾事故现场时间的因素很多，如车流量、车道数、时间段、路面状况等等。将救援时间最短作为最优目标，相应的道路权重如何标定是一个非常值得研究的问题。一般而言，确定以出行时间度量的道路权重建议采用以下方案：引进表征路段行程时间与交通流量之间关系的路阻函数模型以及交叉口延误模型，计算当前时段的路段行程时间及交叉口延误，以此确定道路权重。这样既考虑了

44、交通流的特性，体现了实时因素，又在当前基础设施状况允许的范围内。该方案较好地反映了现实情况，且技术上切实可行，综合考虑了实用性与可行性12。因此，本文选取时间作为路径权值的最优指标，并用路阻函数求出道路交通网中各路段的权值，在此基础上利用Dijkstra最短路径算法实现消防力量调集的最优化。消防中心1245火源3图 4-1 消防中心救火路径图二、Dijkstra最短路径经典算法及分析（一）问题定义讨论的问题是城市消防单源点的最短路径，即对于给定带时间权的无向图G、源点Vi和终点Vj，求得源Vi和终点Vj之间路径中的最短路径。（二）Dijkstra算法设定一个辅助向量Di。Di表示当前从源点V到

45、每个终点Vi的最短路径的时间长度。它的初始值为：如果V到Vi有直接相联的路径，则Di为这条路径的时间权值。否则，设定Di=，设Dj=minDi|ViV 。显然，Dj为从V出发的一条最短路径。下一条次短路径的长度一定是：Dj = minDi|ViV- S ，其中S为已求得最短路径的终点的集合。根据对以上求出的最短时间路径序列的查询，我们可得出两地的最短时间路径13。（三）Dijkstra算法优化及分析1优化Dijkstra算法的思路根据以上对Dijkstra算法的分析，我们可以知道，当n较大时，Dijkstra算法的运行时间急剧增加。如果能有效地减小n值，就能大大地减少运行时间，提高效率。基于以

46、上考虑，为了有效地减小n值，我们把需要计算两节点最佳时间路径的公路网图分成若干个子图，对每个子图分别采用Dijkstra算法进行计算，再把每段计算的节点连接起来，就是我们需要的结果。在把一个图划分成若干个子时遵循以下原则：（1）根据几何中关于两点间的时间距离最短的原理，我们用直线连接源点和终点，最佳路径一般情况应在这条直线附近。划分子图应顺着这条直线来进行14。（2）每个子图应尽可能均匀，即每个子图的节点数基本上接近。否则，本优化算法效果不明显。如果在划分子图时，每个子图的节点数相差悬殊，则子图查找效率低，造成优化算法效果不明显。（3）划分子图尽可能使图的边接近连接源点和终点这条直线附近，以减

47、少重复计算的次数，提高命中率。2优化Dijkstra算法的描述（1）依据以上原则，把一个公路网图划分成若干个子图。（2）划分时，每个子图的节点最接近连接源点和终点的直线。（3）分别对每个子图采用Dijkstra算法进行计算。（4）我们把相邻子图的源点和终点分别进行核对。如果前一子图的终点就是后一子图的源点，那么我们连接这两段，并且认为这段就是最佳路径中的一段；如果前一子图的终点不是后一子图的源点，那么我们修改前一子图的终点，把它定义成后一子图的源点，再对前一子图采用Dijkstra算法进行计算，同时，修改后一子图的源点，把它定义成前一子图的终点，再对后一子图采用Dijkstra算法进行计算，连

48、接这两段。根据计算结果，取这两段中权值最小的一段，作为最佳路径中的一段15。（5）重复以上步骤，直到找出连接源点和终点的最佳路径。采用以上方法找出的路径不一定是最短路径，但它是最接近或就是最短路径16。结论本文基于Dijkstra算法，针对Dijkstra算法在实际应用中搜索速度慢，搜索效率低，时间花费多的的缺陷，对其进行了优化。优化算法只对最短路径上节点的邻居做处理，而不涉及到其他节点，每个搜索过程不必全部遍历或者较少地遍历临时标记点，既缩小了搜索范围，又保证了遍历搜索100%的搜索成功率，从而提高了搜索效率，节省了时间，适应网络拓扑的变化，性能稳定。参考文献1 董鑫,郑逢斌,李莘莘.Dij

49、kstra算法的改进及其在警用GIS中的实现N.郑州轻工业学院学报(自然科学版),2007(4).2 徐寅峰,刘明,苏兵.不完全信息下交通网络最短路径的求解方法J.中国科技论文在线.2005,3(2):46-52.3 焦学军,秦奋,王海鹰.A星算法在城镇地价评估中的应用J.科苑论谈.2008,2(3):103-109.4 张宁.遗传算法的特点及其应用J.中国科技论文在线.2005,3(4):107-111.5 李擎,谢四江,童新海,王志良.一种用于车辆最短路径规划的自适应遗传算法机器与Dijkstra和A*算法的比较N.北京科技大学学报,2006(3).6 罗理,王锋.基于Dijkstra的最

50、短路径改进算法N.湖北汽车工业学院学报,2007(3).7 ZhangYongLong, Dijkstra shortest path algorithm optimization J. Journal of nanchang institute,2005,1(2):23-25.8 陈尹军,王翠玲.基于Dijkstra算法的公路网最短路径查询实现J.中国科技论文在线,2008,2(2):122-127.9 夏华丽,宁书年.Dijkstra算法在物流配送运输规划中的最短路径研究J.中国科技论文在线,2009,3(2):21-23.10 古凌岚.GIS最短路径分析中Dijkstra算法的优化J.计

51、算机与数字工程,2006,34(12):3-7.11 冯桂莲.基于Dijkstra算法的最短路径的实现N.青海大学学报(自然科学版),2007(3).12 陈益富,卢潇,丁豪杰.对Dijkstra算法的优化策略研究J.计算机技术与发展, 2006,12(3):109-112.13 王涛,李伟生.最短路径子图N.北方交通大学学报,2004(2).14 李玲,刘正纲,张强.基于Mapx的最短路径选择算法的实现J.中国科技论文在线,2008,3(2):11-15.15 CaoYang. Data structure the realization of the shortest path algor

52、ithm J. 2007,5(9):12-21.16 IEEE Standard VHDL Language Reference Manual IEEE Press ,1987:28-39. 附录一1、有向边类，class Edge/抽象边类，用于描述道路using System;using System.Collections.Generic;using System.Text;namespace WindowsApplication1 / / 有向边类 / class Edge /抽象边类 private string s_StartNodeID=N/A; /起点 private stri

53、ng s_EndNodeID = N/A; /终点 private double s_Weight=1; /权值，代价 public string StartNodeID get return this.s_StartNodeID; set this.s_StartNodeID = value; public string EndNodeID get return this.s_EndNodeID; set this.s_EndNodeID = value; public double Weight get return this.s_Weight; set this.s_Weight = value; 2、节点类，cla