Dijkstra最短路径算法的优化和改进

1、本科毕业设计（论文）Dijkstra最短路径算法的优化和改进随着计算机和地理信息科学的发展，GIS （地理信息系统）的应用领域越来 越广.最短路径分析是GIS地理网络分析功能中的一个关键性的问题.计算最 短路径的经典算法之一就是Dijkstra算法，许多工程中解决最短路径问题都是采 用这种算法.然而，传统的Dijkstia算法在求解节点间最短路径时，对已标识节 点外的大量节点进行了计算，从而影响了算法的速度.该算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为 止.Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本 内容有详细的介绍.本文在传统Dijkstia

2、算法的基础上，对其进行了优化，此优 化算法只对最短路径上节点的邻点做了一些处理，从而不涉及到其他的一些节 点.提出的优化算法在更新最短路径值与选择最短路径值最小的节点时，仅仅涉 及到节点的邻居集合及已标识集合中所有节点的邻居集合与己标识集合的差集， 其运行时间取决于转接点的邻居集合的元素数量多少.通过减小算法中成功搜索 的搜索范围和改进算法的存储结构这两个主要的研究方向使算法得到优化.因 而，此优化算法在计算的节点数较传统算法大幅减少，提高了算法的速度.本文 通过实验和实际应用对改进后的算法进行了简单的验证.之后将一些算法的改进 和实际例子相结合，这样就能使文章中算法的优化更为理想.关键词最短

3、路径；Dijkstra；优化算法-I-AbstractAbstractWith the development of computer and geographic infoimation science, the applications of GIS (Geographic Iiifbimation System) are becoming more and more widely. However, shortest path analysis is the key problem of network analyses, Dijkstra algontlun is a classic

4、antlunetic for the shortest path. It is the academic foundation that many engineenngs were solved in the shortest path is use. When a shortest path between nodes is searched with Dijkstra algontlun, a lot of nodes away from lagged nodes are involved, so that the efficiency of Dijkstra algontlun is l

5、ow.Main features of the algontlun is the starting point as the center outward expansion layers until it extended to the end point. DijkstiHs algoiitlun is veiy repiesentative of the shortest path algoiitlun, in many professional courses m the basic content as desciibed in detail. The proposed algoii

6、tlun updates the shortest path in the value of the minimum value of the shortest path to the node, only the set of neighbors of the node related to the identified set and a neighbor set of all nodes m the identified set with the set difference, its nuuiing time depends transfei the contact elements

7、of the set of neighbors of quantity. Successful search algontlun by reducing the search range and unpioved algontlun storage stnictuie of these two mam lesearch directions to optimize the algoritlmi. Theiefoiejlie number of processed nodes is largely reduced m the optimization algontlun, and efficie

8、ncy of the optimization algoiitlun is unproved. The improved algontlun is proved to be conect and efficient by expeimients and practical application. After some of the algontlun and the combmation of practical examples, so you can make the ailicle more ideal algontlun optimization.Keywords The short

9、est path； Dijkstra； Optimization algontlun-ii -目 录方. .I TOC o 1-5 h z AbstractIIU. Ill HYPERLINK l bookmark2 o Current Document 第1章绪论1 HYPERLINK l bookmark4 o Current Document 国内外最短路径算法的发展及其概况1 HYPERLINK l bookmark6 o Current Document 传统Dijkstra算法仍然存在的一些问题1 HYPERLINK l bookmark8 o Current Document 本

10、文工作2第2章Dijkstra经典算法3 HYPERLINK l bookmark10 o Current Document 引言3 HYPERLINK l bookmark12 o Current Document 原理及应用3原理3应用5 HYPERLINK l bookmark14 o Current Document Dijkstia算法与其他主流算法的比较6 HYPERLINK l bookmark16 o Current Document 搜索速度比较6 HYPERLINK l bookmark18 o Current Document 搜索成功率比较7Dijkstra算法的优缺点

11、8 HYPERLINK l bookmark20 o Current Document 第3章两点间最短路的改进的Dijkstra算法及其MATLAB实现9Dijkstia 矩阵算法 19Dijkstia 矩阵算法 II9 HYPERLINK l bookmark24 o Current Document 第4章基于Dijkstia算法的优化算法的研究13 HYPERLINK l bookmark26 o Current Document 几种优化算法13 HYPERLINK l bookmark28 o Current Document 减小算法中成功搜索的搜索范围13 HYPERLINK

12、l bookmark30 o Current Document 改进算法的存储结构13 HYPERLINK l bookmark32 o Current Document 本文对Dijlstra优化算法研究14 HYPERLINK l bookmark34 o Current Document 优化目标14 HYPERLINK l bookmark36 o Current Document 优化思路14-in- TOC o 1-5 h z HYPERLINK l bookmark38 o Current Document 问题描述15 HYPERLINK l bookmark40 o Curr

13、ent Document 算法特点19 HYPERLINK l bookmark42 o Current Document 优化和改进的结论20 HYPERLINK l bookmark44 o Current Document 第5章Dijkstia算法在物流上的应用21 HYPERLINK l bookmark46 o Current Document 最优配送路线选择问题22 HYPERLINK l bookmark48 o Current Document 改进的Dijkstra算法在最优配送路线确定中的实例24 HYPERLINK l bookmark50 o Current Doc

14、ument 路径优化结果26结论28 HYPERLINK l bookmark54 o Current Document 参考文献29致谢30附录31-IV -第1章：绪论第1章绪论最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很 多种，其中传统的Dijkstia算法一般用于计算一个源节点到所有其他节点的最小 代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划 等领域都应用广泛.国内外最短路径算法的发展及其概况最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多 科学家在研究.但给出求解的基本思想的人直到1959年才出现，是一位名叫 Eds

15、gei Wybe Dijkstia （迪杰斯特拉）的荷兰计算机科学家，他不仅给出了求解的 基本思想，还给出了算法.他给出的算法主要解决的问题是从某一个固定的点到 其他各点的最短路径问题.后来这个算法被誉为一代经典，被称作Dijkstia算 法.后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定 情况下.确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其 中1958年的Bellman算法、1959年的Dijkstia算法、1969年的DieyfUs算法已成为确 定情况下的经典算法臼.而不确定情况下对最短问题的研究乂分成了四个方面： 研究路段长度随机变化的最短路径问题，

16、以Fiank和Muchandani为代表；研究不 同费用函数最短路径问题，以Loui、Muethy和Saikai为代表；研究时间独立情况 下的路段长度随机变化的最短路径问题，Hall、LiPmg Fu. L.R.Rilett, Elise和Hani 为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表.其 中，第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将 边的权重用期望值表示的最短路径问题”.传统Dijkstia算法仍然存在的一些问题原始Dijkstia算法在存储图形数据和运算时，基于网络的权矩阵，需要根据 其节点与距离之间的关系，形成关联矩阵、

17、邻接矩阵与距离矩阵，需要定义NxN东北电力大学本科毕业论文的数组来存储数据，其中N为网络的节点数，当网络的节点数较大时，将占用 大量的计算机内存.原始Dijkstia算法在运行时一般将网络节点分为未标记节点、临时标记节点 和永久标记节点3种类型.网络中所有节点首先初始化为未标记节点，在搜索过 程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记 节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点 或者所有节点都成为永久标记节点才结束算法.根据算法的描述可知对临时标 记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率.13本文工作随着社会的不断

18、进步，最短路径算法在人们的日常生活显得越来越重要.每 天开车去上班，应该选择哪条公路才能使自己到公司的费用最低、时间最少，这 是最短路径的问题；在网络路由中，怎样选择最优的路由路径，这也是最短路径 问题；在交通旅游、城市规划以及电网架设中怎样使其耗费的资金最少，这还 是最短路径问题.由此可见对最短路径问题的研究是非常有意义的.第2堂Dijkstia经典算法第2章Dijkstra经典算法引言Dijkstia算法是典型最短路算法，用于计算一个节点到其他所有节点的最短 路径.主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点

19、很多，所以效率低，.如 何改进这一经典算法，成为了实现图论中赋权图中解决实际问题的重要课题.原理及应用Dijkstia（迪杰斯特拉）算法是典型的单源最短路径算法，用于计算一个节点 到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展，直到扩 展到终点为止.Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中 都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等.Dijkstia 一般 的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE 表的方式，这里均采用永久和临时标号的方式.该算法要求图中不存在负权边.原理Dijkstia算法是1959年

20、由E. W. Dijkstia提出的图论中求最短路径的一个著名 的算法，使用其可以求得图中一点到其他各顶点的最短路径.原始的Dijkstia算 法将网络结点分成3部分：未标记结点、临时标记结点和永久标记结点.网络中 所有结点首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的 结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短 的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结 点来结束算法.假设每个点都有一对标号（吗，pj，其中吗是从起源点s到点，的最短路 径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；东北电力大学本

21、科毕业论文P,则是从S到/的最短路径中/点的前一点.求解从起源点i到点J的最短路径 算法的基本过程如下：(1 )初始化.起源点设置为:% = 0, p$为空;所有其他点:VV. = 8 , Pj = ?； 标记起源点S ,记女=S,其他所有点设为未标记的.(2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置:% =11皿帆,叫+dj式中，九是从点k到J的直接连接距离.(3)选取下一个点.从所有未标记的结点中，选取力中最小的一个i：h; = nuii ,(所有未标记的点J ),点，就被选为最短路径中的一点，并设为 己标记的.(4)找到点i的前一点.从已标记的点中找到直接连接到点i

22、的点广，作为 前一点，设置：z = j*.(5)标记点i.如果所有点已标记，则算法完全推出，否则，记k=i,转到 (2)再继续.第2堂 Dijkstra经典算法表2-1 0节点到4节点的最短路径循环红点集sK。0“3阳力。4初始化0)一01000301001(0,11010603010020,1330105030903(0X3,22010503060403,3,2,440105030602.2.2应用给定简单定简单无向图G,指定一顶点匕为起点，对于任意 匕&G且年人 求匕到匕的最短路径的长度.例：某单位使用一台设备，在每年年初，企业部门领导都要决定是购置新设 备代替原来的旧设备，还是继续使用旧

23、设备.若购置新设备，需要支付一定的购 置费用；若继续使用旧设备，需支付一定的维修费用.设该种设备在每年年初的 价格（万元）见表2-2使用的不同时间（年）的设备所需要的维修费用（万元） 见表2-3.问如何制定一个五年之内的设备更新计划，使总费用最少.表2-2价格表第i年12345价格1112131213表2-3维修费用表使用年数XX1lx22 cx33 x44x5维修费用5681118东北电力大学本科毕业论文图2-2赋权有向网络图用点0表示“第i年年初购进一台新设备”这种状态，1=1, 2,，5,用匕 表示第五年底的状态.对于每个，=1, 2,，5从匕到匕+；匕各画一条弧, 弧（匕，V.）表示在

24、第1年年初购进一台设备一直使用到第/年年初（即第J 1年 底）.每条弧的权可按已知的数据计算出来，例如（乂，匕）表示第一年年初 购进一台新设备，需支付11万元，一直使用到第三年年底，需维修费（5十6十8） 万元=19万元，故其上的权为30.这样就可以得到一个赋权有向网络，如图2-3所示，所求问题等价于需找从匕 到匕的最短路问题.用Dijkstta算法求解，最优解为（匕，匕，匕），即分别在 第1、4年年初购买一台新设备，总费用为53万元.上述为Dijkstia最基本的求解 路径的方法.2.3 Dijkstia算法与其他主流算法的比较搜索速度比较对5张图分别采用Dijkstia算法、A*算法、遗传

25、算法进行路径规划，他们各 自花费的时间如表2-4所示.第2章 Dijkstra经典算法表2K算法速度对比图节点数搜索速度Dijkstra 算法遗传算法A*算法1612132442437636215957825127由上表可以看出：当地图节点个数和弧的条数比较少时，三种算法所花费的 时间差不多，当节点个数和弧的条数比较多时，A*算法最快，遗传算法其次， Dijkstta算法最慢，而且这种差距将随节点和弧数量的增加而变得更加明显.对 于实际地图而言，由于节点与道路的数量一般都很的大，Dijkstia算法在搜索速 度方面弱势明显.搜索成功率比较对于具有个节点的地图，其待规划节点的个数为-1 （除起点

26、节点外，其 他均可作为待规划节点），由于每个待规划节点对应于一条最短路径，所以对每 张具有个节点的地图而言，应该规划出-1条最短路径.对5张地图分别采用三种算法进行路径规划，三者各自搜索到最短路径的情 况如表2-5所示.表中括号外数据为各算法实际得到最短路径数，括号内数据则 为各算法实际得到路径数和应该规划出的最短路径数-1之比.表2-5三种算法在搜索质量方面的对比节点数Dijkstra 算法A*算法遗传算法1615(100%)12(80%)15(100%)3231(100%)25(81%)29 (94%)4342(100%)32 (76%)38(90%)6261(100%)40(66%)56

27、(92%)7877(100%)45(58%)71(92%)-7 -东北电力大学本科毕业论文由表2-5可以看出：当地图节点个数和弧数量比较多时，Dijkstia算法是一 种遍历算法，每次能保证100%搜索到最短路径，遗传算法搜索到最短路径的成 功率比Dijkstia算法低一些，A*算法最低，且这种差距在节点数和弧数量越大 时更加明显.Dijkstra算法的优缺点Dijkstia算法能够保证100%找到最优解，但其搜索速度较慢，搜索效率非常 低，时间花费较多，一般只能用于离线的路径规划问题.如节点数为的图，用Dijkstia算法计算最短路径总共需要迭代-1次，每次 迭代都新加一个节点到临时节点集合

28、中，由于第1次迭代时不在临时节点集合中 的节点数为-匚即第i次迭代需对个节点进行处理，因此其所需的处理数 为：(，-)=竽/=! ,对n个节点网络的时间复杂度是0(r).在实际应用当中，使用Dijkstia算法 查找最短路径时耗费大量的时间进行数据的比较，本文对Dijkstia算法进行分析, 通过改变算法实现减少不必要节点计算的时间，提高算法的效率达到对其进行优 化.第3章 两点间最短路的改进的Dijkstra算法及其MATLAB实现第3章两点间最短路的改进的Dijkstra算法及其MATLAB实现Dijkstia矩阵算法IDijkstra矩阵算法I比Dijkstra算法更容易在计算机上实现，

29、它能够计算加权 图中任意两顶点之间的最短距离.该算法的基本思想是将加权图G(V,E)存储在 矩阵A = (%，“里该矩阵可定义为0,若i = J% = , %，若iw j,顶点匕与Vj有连边今若iwj,顶点匕与无连边其中，为图G的顶点个数，叫为边匕匕的权重.将Dijkstra算法的思想影响用于此矩阵的第k行，可求出顶点收到其他各项 点的最短距离，将最短距离仍保存在矩阵A的第k行，其中k=1, 2,.当 算法结束时，矩阵A的元素值就是任意两顶点之间的最短距离.Dijkstia矩阵算法nDijkstra矩阵算法I只是简单地将Dijkstra算法的思想应用到矩阵的每一行, 这样做有很多的重复计算，效

30、率不高.为了提高效率，有提出了下面的Dijkstia 矩阵算法H,步骤如下：步骤1输入加权图，存储在矩阵A = 里： U /nxrt步骤2对矩阵A进行操作，求任意两顶点间的最短距离.算法的求解过程; 循环k以1为步长，从1到-1,执行， 一1,2,，&- 1,k + 1,女 + 2,，,kk length (b),东北电力大学本科毕业论文a_id k ;bl k + l,k + 2, ,；kkl length(bl)；循环.反复执行下列语句，直到尿=0；循环.J以1为步长，从1到kkl,执行；若 fe a(k,bl(j),a(k,bl( j) - temiid - 1循环.J以1为步长，从2到

31、&,执行若女力(1) a(k,bmiid j.a_id b(miid)；b b(l: nuid -l),b(tniid +1: kk)；%在数组瓦中去掉一个元素kk k ,执行miid 1 find (bl = a_id)；bl 1(1: mi id 1 -1), bl(niiid 1 +1: kkl)循环.J以1为步长，从攵+ 1到“，执行步骤3则算法结束.算法H与算法I比较，在步骤循环的次数随着我的增加而减少，循环体的执 行总次数会减少一半.Dijkstra矩阵算法II的MATLAB实现见附录.3.2.1简单实例第3章.两点间最短路的改进的Dijkstra算法及其MATLAB实现我们举下面

32、图3-1中顶点匕到其他顶点的最短距离这个例子.图3-1实例图用MATLAB求解的主程序如下：n=12;a=ones (n) +inf;for i=l:na (i,i) =0;enda(l,2)=5;a (2,3) =8;a (2,6) =5;a (3,4) =3;a (3,9)=10;a (4,5) =5;a (4,7) =3;a (5,6) =2;a (7,8) =2;a (8,9) =4;a (8,11)=6;-11 -东北电力大学本科毕业论文a (9,10) =3;a(10Jl)=5;a(10J2)=3; dij2_m(a)计算结果如下:匚，c 12x12 dcuble123456789

33、101112105131612101921232627292508117514161821222d31380310681013141641611305735?12111551278502810IX171620610510720101216191822719146381002598128211685101220476109231810914166Inf38，1026211312171997305311272214111618868508122924161520*12106380图3-2运行结果第4章 基于Dijkstra算法的优化算法的研究第4章基于Dijkstra算法的优化算法的研究几种优化算

34、法减小算法中成功搜索的搜索范围减小算法中成功搜索的搜索范围以尽快到达目标节点.在对现实问题中的交 通图初始化为网络拓扑图时，虽然终点已知，而源点尚未确定，但依据常识离案 发地段最近的派出所应为案发地段所在辖区派出所，或其周边派出所，也就是源 点的选取范围可以确定.利用MapObjects2组件提供的MapLayei.SeaichExpiession （expression）记录集筛选方法，根据案发地段（终点）的不同，动态选取案发 地段所在辖区及相邻辖区的道路图层及派出所图层数据进行最短路径查询，从而 有效地减少了拓扑图中节点总数的值.改进算法的存储结构在实际工作中，还要建立起空间数据结构.网络

35、数据结构使用的是“边和节 点”的数据结构，该数据结构是建立在图论的基础上，节点可用来定义边的连接 关系.对于网络数据的存储，传统的是采用图论中的邻接矩阵方法，其存储量为 NxN（N为网络中节点数）.通常的地理网络，尽管节点很多，但与节点相关联 的节点数目并不多，一般都为稀疏图，将会浪费大量的空间.若采用邻接表的链 式存储结构，其存储量为E（E为节点列表中，同节点关联的所有边的数目），可 节省大量的存储空间，尤其是在表示与节点和边相关信息较多的地理网络时，更 为有效.但邻接表却难以判断两节点之间的关系，因此本文提出利用.NET框架 提供的特殊类Hashtable. NET框架包含特殊类，比如通常

36、所说的集合类用于存储 对象.与数组类似，集合类可以把对象放入容器中，然后再取出.但集合的使用 方法与数组不同，拥有用于插入和删除项的专用方法.使用Hashtable最大的优点 就是大大降低数据存储和查找的时间花费.-13-东北电力大学本科毕业论文本文对Dijlstia优化算法研究优化目标Dijkstra算法用来求解图上从任一节点（源点）到其余各节点的最短路径.其 时间复杂度为0（r）;采用邻接矩阵存储网络拓扑结构，需要（NxN）的存储空 间，随着节点数N的增大，其计算效率和存储效率越低.针对此问题，提出了 Dijkstra算法的改进，本文在对传统Dijkstra算法分析的基础上，对其进行了优

37、化，优化算法只对最短路径上节点的邻居做处理，而不涉及到其他节点.优化思路Dijkstia算法基本方法：设必是从源点s到节点j的最短路径长度；p ,是从s到 /的最短路径中/点的前一节点,S是标识集合；T是未标识集合；M是节点集 合.乙是节点i到节点）的距离（i与/直接相连，否则匕=8）,算法步骤如 下：StepO： S = s; T = M-S； VV. =（ jgT, s 与j直接相连）或% = 8 （） 7，s与）不直接相连）.Stepl：在T中找到节点i,使s到i的距离最小，并将，划归到S （可从与s直 接相连的）中考虑）若djmm内，）与s直接相连，则将i划归到S中，即5 = 甲, T

38、 = T-i； jeT； Pj = S .Step2：修改T中/节点的匕值：Wj = imi（叱,+1匕+%）；若VV.值改变，则p =/. jwT ； ieS .Step3：选定所有的%最小值，并将其划归到S中：W； = minW,； S=5u/； T=T-i；若卜| 二 “,所有节点已标识，-14-第4章 基于Dijkstra算法的优化算法的研究则算法终止，否则，转入Step2.通过分析传统Dijkstia算法的基本思路，传统Dijkstia算法存在如下两点不足: (1)当从未标记节点集合TT中选定一个节点k作为转接点后时，需扫描未 标记节点集合T中的节点,并更新其W,值，而未标记节点集合

39、T中往往包含大量 与转接节点k不直接相连的节点i (即4, = 8);(2)在未标记节点集合T中选择一个堆值最小的节点作为下一个转接节点, 然而下一个转接节点往往是与标记节点集合S中的节点直接相连的.问题描述基于上述两点不足，对传统Dijkstia算法进行优化，算法优化思路为：首先 从源点s的邻居集合集合N纥(与s直接相连的节点集合)中选择距离最小的邻居 节点k作为转接点，同时将划归到标识集合S (初始时，S为s).然后对k邻 居集合与标识集合的差集中节点的值进行更新，从标识集合s中所有节点的邻居 集合的并集与标识集合的差集(uNaS , ieS)中选择一个M值最小的节点作 为下一个转接点，并

40、划归到标识集合s中.重复上述过程，直到所有的节点都被 标识过，即卜|二，算法结束.设Ng为节点，的邻居集合；S为标识集合；明是从源点s到节点)的最短 路径长度；号是从s到1的最短路径中，点的前一节点：4是节点i到节点j的 距离.算法步骤如下：StepO：初始化 S = s； vv. = dxi (/ e NBs)；否则吗=8(i 为 Pt= s .Stepl：若九二min%, S = S 2 = w2,w5 = niii vv5,vv4 + d45= niii 松,3 = 3 2 = 匕， 卬6 = nun限,%+九 = svv7 = nmi 卬7，卬4 + J47) = oonmi w. =

41、 h = 2 ,J -S = （l”匕，匕，匕），7 = 63，匕，16,匕）;16第4章 基于Dijkstra算法的优化算法的研究Step3： T =（匕,v5，v7）vv3 = niii 卬3,w2 +d2Z= niii 5,5 = 5 , TOC o 1-5 h z w5 = niii vv5，卬2 + ? = nmi 3,8 = 3 4 =%=w6,若为明nmi Wj = vv3 = w6 = 4 ,二 S =（匕，匕，匕，匕，%），T = （v6,v7）；Step5： T = （v6,v7）w6 = niii vv6,吗 + 右 = nin 4,8 = 4 ,w7 = niii 卬7

42、, vv3 + J37）= niii 5,8 = 5 4 = w6,v 111111 = = 4,S =（匕.匕,%，%,%，%），丁 =（匕）；Step6 ： T = （v7）vv7 = niii卬7,w6 +d67= niii5,6 = 5 至此，算法终止.结果为卬2 = 2, % = 4,*=2,叼=3 ,叫=4, % = 5 .东北电力大学本科毕业论文优化Dijkstia算法求解过程：表4-1优化的Dijkstra算法求解巧到其他各节点最短路径的过程迭代选代数匕 匕匕匕匕 乙 匕定 ”叫点01252- 匕 卬=0（匕，匕，叱）1-25- 匕 % =2（匕，vz，匕，v5）2- 4-3-

43、 匕 w2 =2（匕，匕，匕）3- -4- 匕 叼=3（匕，匕，v6, v7）4- -45 匕 *=4 （匕，匕，匕，心，口6）5- -5 v6 vv6 =4（v3, v5, v7）6- - V7 vv7 =5（V5, v6）StepO：初始化s =（匕），与匕直接相连点有匕，%,办，NS】=（匕，匕,也），叼=0；Step 1：卬4 = d4 = nun4, =2,5 = （, v4）, j e NB1=（匕，匕，0,%）, B4-5 = （v2,v3,v5）, uN54-5 = （v2,v3,v5）；Step2： jg N54-5 = （v2,v3,v5）w2 = nm vv2,卬4 +

44、J42 = niii 2,4 = 2 ,vv3 = niii 卬3，卬4 + J43 = niii 5,5 = 5 2 = w2,w5 = niii 卬5, vv4 + 45= nin 松,3 = 3 2 = w2,minnmi w：=m=2 ,J-，S =（匕，匕，匕），人/2 =（匕,匕,巳），NB2-S = （v3）, dN6?S =（匕,）Step3 ： j e l）NB? - S =（匕,v5）18第4章 基于Dijkstra算法的优化算法的研究卬3 = nin 卬3 /匕 +/23= niii 5,5 = 5 ,明=3 4 = vv3,若为明, nun吗=*=卬6 =%，S=（匕匕

45、，匕，匕，%）,仍3 =（匕.匕#4，%，也），NBb-S = M）,uA3-S = （v6,v7）；Step5： j2NBS = （v6,v7）卬6 =4；* =54=卬，, nunWj = vv6 =4, S =（匕2,匕 #4#5#6），凡线=（匕匕），NB6-S = （v7 ）,UN叫-S =（匕）；Step6： jwNBe-S = W）w7 = nrni %,M% + 7 = 6,6 = 5 .至此，所有节点已标识，则算法终止.最终结果为叭=2, % = 4,%=2, w5 = 3 , w6 = 4,卬7 = 5 -19-东北电力大学本科毕业论文4.2.4算法特点传统Dijkstia

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

47、 (根为边数，为顶点数)，一般在GIS的网络图中，e g 2,5,n由于Step2、Step3都是搜索与匕(/=1, 2, 3,，)相邻的结点操作,时间复 杂度均为。);Step3的时间复杂度为0(,即0(xe)； Step5的时间复杂 度为0(xe).因此，算法的时间复杂度为0(xe).4.3优化和改进的结论由图4-1对带权值的无向图G7的求解可以看出，优化了的Dijkstta算法在 Step2和Step3中较经典的Dijkstia算法减少了步骤(4-1) (4-2) (4-3) (4-4), 减少了计算次数，提高了搜索速度.当网络拓扑结构图具有的节点数，I，较大且 其关联矩阵为一个稀疏矩阵

48、时，相对传统Dijkstia算法，优化算法大大减少了计 算次数与比较次数，在一定程度上提高了运算速度.在分析传统Dijkstia算法的 基础上，针对传统Dijkstia算法存在的两点不足之处，对其进行了优化处理.当 网络的规模较大及其关联矩阵为一个稀疏矩阵时，本文提出的优化算法，与传统 Dijkstia算法相比，能大大减少了计算次数及比较次数，提高了运算效率.-20-第5章Dijkstra算法在物流上的应用第5章Dijkstra算法在物流上的应用物流成为一项产业的历史并不久远，最早是起源于二战中美军建立的后勤理 论原型，当时的后勤是指将战时物资生产、采购、运输和配给等活动作为整体进 行统筹安排

49、，以达到使战略物资补给费用最低，速度最快，效率更高的目的，后 来后勤体系逐渐被经济领域采用，形成现代物流系统.尤其在科学技术突飞猛进, 经济全球化迅速发展的今天，物流产业已经形成了庞大的规模和网络，并成为社 会发展的基础产业和经济推动力.物流服务已经融入到社会经济生活的各个角落，一方面，企业与企业之间的 不可能孤立存在，多数情况是相互依存相互合作并形成一条完整的产业链条，企 业与企业的合作就会产生大量的物资运输和交换需求，这就需要高效有力的物流 纽带将之连接起来.另一方面，随着电子商务产业的发展，面对小宗单一客户的 服务需求呈爆炸式增长，物流领域的效率直接影响到电子商务产业的效益.然而物流产业

50、的发展也面临着很严重的供求矛盾和产业发展瓶颈以及竞争 压力.面对飞速增长的服务需求，物流产业的基础设施和物流能力难以消化，服 务订单的堆积也导致了物流效率的低下.这就要求物流企业从自身上进行硬件设 施升级和管理方法上的创新.由于硬件升级上的成本投入巨大，以及回报周期的 长效性，很难再短期内提高企业的竞争力，越来越多的物流企业将目光投在了优 化配送网络，提升管理水平方面.同等基础条件下，一个企业的配送网络是否达 到最优，资源使用是否达到了最大效率，直接关系到物流服务效率的高低以及企 业竞争力的大小.对于物流企业来说，物流网络的范围和质量直接关系到其配送 能力的高低和自身服务质量的好坏，进而直接影

51、响到企业核心竞争力的大小.因 而，为了提升物流企业的核心竞争力，我们需要研究出更为有效的管理和分配方 法，充分有效利用现有的人力物力时间等资源，达到最优化配送.为了科学有效 的实现这些目的，就需要引入新的技术来解决问题.计算机技术的发展为各行各 业都带来了显著的效益，在信息化生产的今天，物流行业也急需一种能够全局统 筹监控，自动进行资源调配的计算机系统来对运营网络进行分析控制，以实现良 性运营.首先阐述了物流行业的产生背景和发展，以及其存在的一些问题，并主-21 -东北电力大学本科毕业论文要针对物流企业中存在的一些资源优化调度，区域规划管理等方面存在的问题进 行分析，结合数学建模以及数据挖掘相

52、关技术提出了一种基于改进Dijkstia算 法.最优配送路线选择问题在物流配送领域中，最重要的任务就是如何将货物用最高效，快捷的方式送 达目的地.不同的目的地之间由于客观条件的不同，运送成本也会不同.将不同 节点之间的各项信息进行汇总可以得到一个有权无向图，该图可以全面的反映出 整个物流网络中各个节点间的详细情况.通过对整个物流网络进行分析，我们就 可以权衡确定选择何种配送方式，何种配送路线等.本文中我们采用计算机领域 中对图最短路径分析的方法一一Dijkstia算法对最优配送路线选择问题进行分 析.我们知道，在物流配送环节中首先要形成一条既有的物流网络，能够将任意 配送节点发出的货物高效的送

53、达网络中其他节点.其中节点间的交通长度是客观 成本，会直接影响到相应的人力成本和油耗成本以及损耗成本.我们设两个物流 节点之间的交通长度为W,也就是基础成本.在此基础上会产生附加成本.进一步，我们会讨论附加成本与基础成本之间的关系问题.进而确定每两个 节点间最终的权值.我们知道，由于不同城市的经济发展水平和地理因素等会导 致他们之间的人力成本和油耗成本等因素的不同，有些城市经济水平比较发达， 相应的其人力成本和油耗成本等就会增加，而有些城市之间的交通路况不好，就 会响应的增加油耗成本和损耗成本.故而我们需要对不同城市之间的具体情况进 行深入调查才，采用综合考虑的方法来确定其最终费用阿.此外我们

54、发现，在物流运输过程中，由于两地之间的人力成本不同会导致双 向运输中的成本统计出现不同，因此，在本文中，我们仅取折中的办法，统计两 地之间双向运输的平均成本.我们设两地的人力成本分别为 、只，我们根据 经验公式可以得出一般运输领域中平均人力成本计算公式：p Pp=p5p”py+pj-22 -第5章.Dijkstra算法在物流上的应用假设针对附加成本方面，我们只考虑运输距离，油耗，和人力成本三个基本 因素.我们设运输距离为W,两个配送节点的油耗成本分别为。,两个配 送节点的人力成本分别为巴、P, L表示货物损耗成本，/表示实时油价，人， 我、，表示基础成本影响人因子，他们分别表示各项附加成本受到

55、基本成本的影 响程度.我们可以得到最终成本R的计算公式为：pP.P = k2w9 L =R = ”(。1片(二+ 片)+。2 P?(=+R) + Lp2P根据不同影响因素及其影响因子我们可以得到两个配送节点之间相应的油 耗成本，人力成本以及可能的损耗成本，进而得到最终的综合成本，也就是两个 配送节点之间的综合权值.我们改进的Dijkstra算法的流程图如图5-1所示：图5-1改进的Dijkstia算法流程图-23 -东北电力大学本科毕业论文改进的Dijkstia算法在最优配送路线确定中的实例为了更好的说明问题，我们选取一个如图5-2所示的简单联通区域为例，进 行分析和说明具体的方案设计.我们可

56、以看到途中一共有七个配送节点，节点之 间的路线权值表明的是两个节点的运输距离.图5-2路线无向有权示意图人力成本和油耗成本列表如表5-1所示，单位为千元/公里吨-24 -第5章Dijkstn算法在物流上的应用表5-1人力成本表人力成本油耗成本A0.350.34B0.370.17C0.420.31D0.380.33E0.790.26F0.510.39G0.350.39各个节点间的联通情况以及运输距离情况也可以列出表格如表5-2所示.表5-2运输距离表ABCDEFGAoB80C60D1530E131100F760G890我们根据以上公式对本例中的配送节点间综合代价进行计算得到了各个配 送节点间的综

57、合权值如图5-3所示：-25 -东北电力大学本科毕业论文路径优化结果继而我们根据上述数据，应用Dijkstra算法对其进行最优配送路径确定，我们 确定选定的最终结果如表5-3所示：-26 -第5章Dijkstra算法在物流上的应用表5-3路径选择图路径选择花费代价A f 6A f 60.72A f C0.66A .。4 .C .。1.04NtC tE0.84A f尸AfCfE一尸2.02A f GA C f E G2.20B fC6 f A f C1.38B f D6 A f C 。1.76B EB A C E1.56B F5 f AfC 一石一尸2.74B G5 f AfC 一石G2.92C tDC tD0.38C tEC E0.18C t FC f E f F1.36C f GC f E fG1.54D E。fC f E0.56D f FD f F1.11D GD C E G1.92E tFE tF1.18E fGE tG1.36F GF tG1.48这样，我们就确定了从任意一个节点出发，配送到区域内其他节点应选择的