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

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业本科毕业设计（论文）Dijkstra最短路径算法的优化和改进学 生 姓 名：。指 导 教 师： 屹专业、 班级：信息院 （系）：理2013 年 6 月 吉 林摘 要随着计算机和地理信息科学的发展，GIS（地理信息系统）的应用领域越来越广最短路径分析是GIS地理网络分析功能中的一个关键性的问题计算最短路径的经典算法之一就是Dijkstra算法，许多工程中解决最短路径问题都是采用这种算法然而，传统的Dijkstra算法在求解节点间最短路径时，对已标识节点外的大量节点进行了计

2、算，从而影响了算法的速度该算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍本文在传统Dijkstra算法的基础上，对其进行了优化，此优化算法只对最短路径上节点的邻点做了一些处理，从而不涉及到其他的一些节点提出的优化算法在更新最短路径值与选择最短路径值最小的节点时，仅仅涉及到节点的邻居集合及已标识集合中所有节点的邻居集合与已标识集合的差集，其运行时间取决于转接点的邻居集合的元素数量多少通过减小算法中成功搜索的搜索范围和改进算法的存储结构这两个主要的研究方向使算法得到优化因而，此优化算法在计算的

3、节点数较传统算法大幅减少，提高了算法的速度本文通过实验和实际应用对改进后的算法进行了简单的验证之后将一些算法的改进和实际例子相结合，这样就能使文章中算法的优化更为理想关键词 最短路径；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 anal

4、ysis is the key 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 fro

5、m lagged nodes are involved, so that the efficiency of Dijkstra algorithm is low. Main features of the algorithm is the starting point as the center outward expansion layers until it extended to the end point. Dijkstras algorithm is very representative of the shortest path algorithm, in many profess

6、ional courses in the basic content as described in detail. The proposed algorithm 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 in the identified set wi

7、th the set difference, its running time depends transfer the contact elements of the set of neighbors of quantity. Successful search algorithm by reducing the search range and improved algorithm storage structure of these two main research directions to optimize the algorithm. Therefore,the number o

8、f processed 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. After some of the algorithm and the combination of practical examples,

9、so you can make the article more ideal algorithm optimization.Keywords The shortest path; Dijkstra; Optimization algorithm目 录 TOC o 1-3 h z u 第1章 绪论最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很多种，其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划等领域都应用广泛1.1 国内外最短路径算法的发展及其概况最短路径在20世纪初开始受到人们的

10、重视，关于它的求解方法，当时有很多科学家在研究但给出求解的基本思想的人直到1959年才出现，是一位名叫Edsger Wybe Dijkstra（迪杰斯特拉）的荷兰计算机科学家，他不仅给出了求解的基本思想，还给出了算法他给出的算法主要解决的问题是从某一个固定的点到其他各点的最短路径问题后来这个算法被誉为一代经典，被称作Dijkstra算法后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定情况下确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法1而

11、不确定情况下对最短问题的研究又分成了四个方面：研究路段长度随机变化的最短路径问题，以Frank和Mirchandani为代表；研究不同费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下的路段长度随机变化的最短路径问题，Hall、LiPing Fu、L.R.Rilett、Elise和Hani为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表其中，第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题”1.2 传统Dijkstra算法仍然存在的一些问题 原始Dijkstra算法在存储图形数

12、据和运算时，基于网络的权矩阵，需要根据其节点与距离之间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义的数组来存储数据，其中为网络的节点数，当网络的节点数较大时，将占用大量的计算机内存原始Dijkstra算法在运行时一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型网络中所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率1

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

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

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

16、下：（1）初始化起源点设置为：,为空；所有其他点:,；标记起源点，记,其他所有点设为未标记的（2）检验从所有已标记的点到其直接连接的未标记的点j的距离，并设置：式中，是从点到的直接连接距离（3）选取下一个点从所有未标记的结点中，选取中最小的一个：，（所有未标记的点），点就被选为最短路径中的一点，并设为已标记的（4）找到点的前一点从已标记的点中找到直接连接到点的点，作为前一点，设置：=（5）标记点如果所有点已标记，则算法完全推出，否则，记=，转到（2）再继续 0 100 10 41 30 10 50 6032 20 图2-1 Dijkstra算法最短路径应用演示图表2-1 0节点到4节点的最短路

17、径循环红点集初始化-010301001101060301002301050309032010503060440105030602.2.2 应用给定简单定简单无向图,指定一顶点为起点,对于任意 且,求到的最短路径的长度例：某单位使用一台设备，在每年年初，企业部门领导都要决定是购置新设备代替原来的旧设备，还是继续使用旧设备若购置新设备，需要支付一定的购置费用；若继续使用旧设备，需支付一定的维修费用设该种设备在每年年初的价格（万元）见表2-2使用的不同时间（年）的设备所需要的维修费用（万元）见表2-3问如何制定一个五年之内的设备更新计划，使总费用最少表2-2 价格表第年12345价格11121312

18、13表2-3 维修费用表使用年数维修费用56811181617185941421718233224233022图2-2 赋权有向网络图用点表示“第i年年初购进一台新设备”这种状态，=1，2，5，用表示第五年底的状态对于每个=1，2，5从到，；各画一条弧，弧（，）表示在第i年年初购进一台设备一直使用到第年年初（即第年底）每条弧的权可按已知的数据计算出来，例如（，）表示第一年年初购进一台新设备，需支付11万元，一直使用到第三年年底，需维修费（5+6+8）万元=19万元，故其上的权为30这样就可以得到一个赋权有向网络，如图2-3所示，所求问题等价于需找从到的最短路问题用Dijkstra算法求解，最优

19、解为（，），即分别在第1、4年年初购买一台新设备，总费用为53万元上述为Dijkstra最基本的求解路径的方法2.3 Dijkstra算法与其他主流算法的比较2.3.1 搜索速度比较对5张图分别采用Dijkstra算法、算法、遗传算法进行路径规划，他们各自花费的时间如表2-4所示表2-4 算法速度对比图节点数搜索速度Dijkstra算法遗传算法A*算法 161232442437636215957825127由上表可以看出：当地图节点个数和弧的条数比较少时，三种算法所花费的时间差不多，当节点个数和弧的条数比较多时，A*算法最快，遗传算法其次，Dijkstra算法最慢，而且这种差距将随节点和弧数量

20、的增加而变得更加明显对于实际地图而言，由于节点与道路的数量一般都很的大，Dijkstra算法在搜索速度方面弱势明显2.3.2 搜索成功率比较对于具有个节点的地图，其待规划节点的个数为（除起点节点外，其他均可作为待规划节点），由于每个待规划节点对应于一条最短路径，所以对每张具有个节点的地图而言，应该规划出条最短路径对5张地图分别采用三种算法进行路径规划，三者各自搜索到最短路径的情况如表2-5所示表中括号外数据为各算法实际得到最短路径数，括号内数据则为各算法实际得到路径数和应该规划出的最短路径数之比表2-5 三种算法在搜索质量方面的对比节点数Dijkstra算法算法遗传算法1615(100%)12

21、(80%)15(100%)3231(100%)25(81%)29(94%)4342(100%)32(76%)38(90%)6261(100%)40(66%)56(92%)7877(100%)45(58%)71(92%)由表2-5可以看出：当地图节点个数和弧数量比较多时，Dijkstra算法是一种遍历算法，每次能保证100%搜索到最短路径，遗传算法搜索到最短路径的成功率比Dijkstra算法低一些，算法最低，且这种差距在节点数和弧数量越大时更加明显2.3.3 Dijkstra算法的优缺点Dijkstra算法能够保证100%找到最优解，但其搜索速度较慢，搜索效率非常低，时间花费较多，一般只能用于离

22、线的路径规划问题如节点数为的图，用Dijkstra算法计算最短路径总共需要迭代次，每次迭代都新加一个节点到临时节点集合中，由于第i次迭代时不在临时节点集合中的节点数为即第次迭代需对个节点进行处理，因此其所需的处理数为：对n个节点网络的时间复杂度是在实际应用当中，使用Dijkstra算法查找最短路径时耗费大量的时间进行数据的比较，本文对Dijkstra算法进行分析，通过改变算法实现减少不必要节点计算的时间，提高算法的效率达到对其进行优化第3章 两点间最短路的改进的Dijkstra算法及其MATLAB实现3.1 Dijkstra矩阵算法 = 1 * ROMAN * MERGEFORMAT IDij

23、kstra矩阵算法 = 1 * ROMAN * MERGEFORMAT I比Dijkstra算法更容易在计算机上实现，它能够计算加权图中任意两顶点之间的最短距离该算法的基本思想是将加权图存储在矩阵里该矩阵可定义为其中，为图的顶点个数，为边的权重 将Dijkstra算法的思想影响用于此矩阵的第行，可求出顶点到其他各项点的最短距离，将最短距离仍保存在矩阵的第行，其中=1，2，当算法结束时，矩阵的元素值就是任意两顶点之间的最短距离3.2 Dijkstra矩阵算法 = 2 * ROMAN * MERGEFORMAT IIDijkstra矩阵算法 = 1 * ROMAN * MERGEFORMAT I只

24、是简单地将Dijkstra算法的思想应用到矩阵的每一行，这样做有很多的重复计算，效率不高为了提高效率，有提出了下面的Dijkstra矩阵算法 = 2 * ROMAN * MERGEFORMAT II，步骤如下：步骤1 输入加权图，存储在矩阵里；步骤2 对矩阵进行操作，求任意两顶点间的最短距离算法的求解过程；循环以1为步长，从1到,执行，；循环反复执行下列语句，直到；循环以1为步长，从1到，执行；若循环以1为步长，从2到，执行若；在数组中去掉一个元素；数组的长度减少了1若，执行；循环以1为步长，从到，执行步骤3 则算法结束算法 = 2 * ROMAN * MERGEFORMAT II与算法 =

25、1 * ROMAN * MERGEFORMAT I比较，在步骤循环的次数随着的增加而减少，循环体的执行总次数会减少一半 Dijkstra矩阵算法 = 2 * ROMAN * MERGEFORMAT II的MATLAB实现见附录3.2.1 简单实例我们举下面图3-1中顶点到其他顶点的最短距离这个例子555381053426533图3-1 实例图用MATLAB求解的主程序如下：n=12;a=ones(n)+inf;for i=1:na(i,i)=0;enda(1,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

26、;a(7,8)=2;a(8,9)=4;a(8,11)=6;a(9,10)=3;a(10,11)=5;a(10,12)=3; dij2_m(a)计算结果如下：图3-2 运行结果第4章 基于Dijkstra算法的优化算法的研究4.1 几种优化算法4.1.1 减小算法中成功搜索的搜索范围减小算法中成功搜索的搜索范围以尽快到达目标节点在对现实问题中的交通图初始化为网络拓扑图时，虽然终点已知，而源点尚未确定，但依据常识离案发地段最近的派出所应为案发地段所在辖区派出所，或其周边派出所，也就是源点的选取范围可以确定利用MapObjects2组件提供的MapLayer.SearchExpression （ex

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

28、)，可节省大量的存储空间，尤其是在表示与节点和边相关信息较多的地理网络时，更为有效但邻接表却难以判断两节点之间的关系，因此本文提出利用NET框架提供的特殊类HashtableNET框架包含特殊类，比如通常所说的集合类用于存储对象与数组类似，集合类可以把对象放入容器中，然后再取出但集合的使用方法与数组不同，拥有用于插入和删除项的专用方法使用Hashtable最大的优点就是大大降低数据存储和查找的时间花费4.2 本文对Dijlstra优化算法研究4.2.1 优化目标Dijkstra算法用来求解图上从任一节点(源点)到其余各节点的最短路径其时间复杂度为；采用邻接矩阵存储网络拓扑结构，需要的存储空间，

29、随着节点数的增大，其计算效率和存储效率越低针对此问题，提出了Dijkstra算法的改进，本文在对传统Dijkstra算法分析的基础上，对其进行了优化，优化算法只对最短路径上节点的邻居做处理，而不涉及到其他节点4.2.2 优化思路Dijkstra算法基本方法：设是从源点s到节点j的最短路径长度；是从到的最短路径中点的前一节点是标识集合；是未标识集合；是节点集合是节点到节点的距离（与直接相连，否则）算法步骤如下：Step0：；（，与直接相连）或(，与不直接相连)Step1：在中找到节点，使到的距离最小，并将划归到（可从与直接相连的中考虑）若= min ，与直接相连，则将划归到中，即，；Step2：

30、修改中节点的值：；若值改变，则；.Step3：选定所有的最小值，并将其划归到中：；若,所有节点已标识，则算法终止，否则，转入Step2通过分析传统Dijkstra算法的基本思路，传统Dijkstra算法存在如下两点不足：（1）当从未标记节点集合T中选定一个节点作为转接点后时，需扫描未标记节点集合中的节点并更新其值，而未标记节点集合中往往包含大量与转接节点不直接相连的节点（即）；（2）在未标记节点集合中选择一个值最小的节点作为下一个转接节点，然而下一个转接节点往往是与标记节点集合中的节点直接相连的4.2.3 问题描述基于上述两点不足，对传统Dijkstra算法进行优化，算法优化思路为：首先从源点

31、s的邻居集合集合（与直接相连的节点集合）中选择距离最小的邻居节点作为转接点，同时将划归到标识集合（初始时，为）然后对邻居集合与标识集合的差集中节点的值进行更新，从标识集合中所有节点的邻居集合的并集与标识集合的差集（，）中选择一个值最小的节点作为下一个转接点，并划归到标识集合中重复上述过程，直到所有的节点都被标识过，即，算法结束设为节点的邻居集合；为标识集合；是从源点到节点的最短路径长度；是从到的最短路径中点的前一节点；是节点到节点的距离算法步骤如下：Step0：初始化；否则；Step1：若，则Step2：修改中的值：；若值改变，则，Step3：选定中的最小值，并将其划归到中：；若；节点已标识，

32、则算法终止，否则，转到Step2图4-1为带权值的无向图，对分别用Dijkstra算法和优化了的Dijkstra算法进行求解，则可得从到其余各节点的最短路径2252233115221图4-1 带权值的无向图经典Dijkstra算法求解过程：Step0：初始化，；Step1：，；Step2：， （4-1） （4-2），,；Step3：， （4-3） （4-4），；Step4：，若为，；Step5：，min= 4，；Step6：至此，算法终止结果为，优化Dijkstra算法求解过程：表4-1 优化的Dijkstra算法求解v1到其他各节点最短路径的过程迭代代数选定点01252-=0(,)1-25

33、= 1 * GB3 * MERGEFORMAT -=2(,)2- = 1 * GB3 * MERGEFORMAT 4-3-=2(,)3-4- = 2 * GB3 * MERGEFORMAT -=3(,)4- = 3 * GB3 * MERGEFORMAT -45=4(,)5- = 3 * GB3 * MERGEFORMAT 5=4(,)6- = 4 * GB3 * MERGEFORMAT =5(,)Step0：初始化，与直接相连点有,，；Step1：2,，；Step2：，min，Step3：，min，；Step4：，若为4，；Step5：4;54，4， ；Step6：)至此，所有节点已标识，则

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

35、点的平均出度（为边数，为顶点数），一般在GIS的网络图中，由于Step2、Step3都是搜索与（=l，2，3,，）相邻的结点操作，时间复杂度均为；Step3的时间复杂度为，即；Step5的时间复杂度为因此，算法的时间复杂度为4.3 优化和改进的结论由图4-1对带权值的无向图的求解可以看出，优化了的Dijkstra算法在Step2和Step3中较经典的Dijkstra算法减少了步骤（4-1）（4-2）（4-3）（4-4），减少了计算次数，提高了搜索速度当网络拓扑结构图具有的节点数，较大且其关联矩阵为一个稀疏矩阵时，相对传统Dijkstra算法，优化算法大大减少了计算次数与比较次数，在一定程度上提

36、高了运算速度在分析传统Dijkstra算法的基础上，针对传统Dijkstra算法存在的两点不足之处，对其进行了优化处理当网络的规模较大及其关联矩阵为一个稀疏矩阵时，本文提出的优化算法，与传统Dijkstra算法相比，能大大减少了计算次数及比较次数，提高了运算效率第5章 Dijkstra算法在物流上的应用物流成为一项产业的历史并不久远，最早是起源于二战中美军建立的后勤理论原型，当时的后勤是指将战时物资生产、采购、运输和配给等活动作为整体进行统筹安排，以达到使战略物资补给费用最低，速度最快，效率更高的目的，后来后勤体系逐渐被经济领域采用，形成现代物流系统尤其在科学技术突飞猛进，经济全球化迅速发展的

37、今天，物流产业已经形成了庞大的规模和网络，并成为社会发展的基础产业和经济推动力物流服务已经融入到社会经济生活的各个角落，一方面，企业与企业之间的不可能孤立存在，多数情况是相互依存相互合作并形成一条完整的产业链条，企业与企业的合作就会产生大量的物资运输和交换需求，这就需要高效有力的物流纽带将之连接起来另一方面，随着电子商务产业的发展，面对小宗单一客户的服务需求呈爆炸式增长，物流领域的效率直接影响到电子商务产业的效益然而物流产业的发展也面临着很严重的供求矛盾和产业发展瓶颈以及竞争压力面对飞速增长的服务需求，物流产业的基础设施和物流能力难以消化，服务订单的堆积也导致了物流效率的低下这就要求物流企业从

38、自身上进行硬件设施升级和管理方法上的创新由于硬件升级上的成本投入巨大，以及回报周期的长效性，很难再短期内提高企业的竞争力，越来越多的物流企业将目光投在了优化配送网络，提升管理水平方面同等基础条件下，一个企业的配送网络是否达到最优，资源使用是否达到了最大效率，直接关系到物流服务效率的高低以及企业竞争力的大小对于物流企业来说，物流网络的范围和质量直接关系到其配送能力的高低和自身服务质量的好坏，进而直接影响到企业核心竞争力的大小因而，为了提升物流企业的核心竞争力，我们需要研究出更为有效的管理和分配方法，充分有效利用现有的人力物力时间等资源，达到最优化配送为了科学有效的实现这些目的，就需要引入新的技术

39、来解决问题计算机技术的发展为各行各业都带来了显著的效益，在信息化生产的今天，物流行业也急需一种能够全局统筹监控，自动进行资源调配的计算机系统来对运营网络进行分析控制，以实现良性运营首先阐述了物流行业的产生背景和发展，以及其存在的一些问题，并主要针对物流企业中存在的一些资源优化调度，区域规划管理等方面存在的问题进行分析，结合数学建模以及数据挖掘相关技术提出了一种基于改进Dijkstra 算法5.1 最优配送路线选择问题在物流配送领域中，最重要的任务就是如何将货物用最高效，快捷的方式送达目的地不同的目的地之间由于客观条件的不同，运送成本也会不同将不同节点之间的各项信息进行汇总可以得到一个有权无向图

40、，该图可以全面的反映出整个物流网络中各个节点间的详细情况通过对整个物流网络进行分析，我们就可以权衡确定选择何种配送方式，何种配送路线等本文中我们采用计算机领域中对图最短路径分析的方法Dijkstra算法对最优配送路线选择问题进行分析我们知道，在物流配送环节中首先要形成一条既有的物流网络，能够将任意配送节点发出的货物高效的送达网络中其他节点其中节点间的交通长度是客观成本，会直接影响到相应的人力成本和油耗成本以及损耗成本我们设两个物流节点之间的交通长度为，也就是基础成本在此基础上会产生附加成本进一步，我们会讨论附加成本与基础成本之间的关系问题进而确定每两个节点间最终的权值我们知道，由于不同城市的经

41、济发展水平和地理因素等会导致他们之间的人力成本和油耗成本等因素的不同，有些城市经济水平比较发达，相应的其人力成本和油耗成本等就会增加，而有些城市之间的交通路况不好，就会响应的增加油耗成本和损耗成本故而我们需要对不同城市之间的具体情况进行深入调查才，采用综合考虑的方法来确定其最终费用此外我们发现，在物流运输过程中，由于两地之间的人力成本不同会导致双向运输中的成本统计出现不同，因此，在本文中，我们仅取折中的办法，统计两地之间双向运输的平均成本我们设两地的人力成本分别为 、，我们根据经验公式可以得出一般运输领域中平均人力成本计算公式：假设针对附加成本方面，我们只考虑运输距离，油耗，和人力成本三个基本

42、因素我们设运输距离为 ，两个配送节点的油耗成本分别为 、,两个配送节点的人力成本分别为、，表示货物损耗成本，表示实时油价，表示基础成本影响因子，他们分别表示各项附加成本受到基本成本的影响程度我们可以得到最终成本的计算公式为：，根据不同影响因素及其影响因子我们可以得到两个配送节点之间相应的油耗成本，人力成本以及可能的损耗成本，进而得到最终的综合成本，也就是两个配送节点之间的综合权值我们改进的 Dijkstra 算法的流程图如图 5-1 所示：选取初始节点人力成本油耗成本综合代价损耗成本更新S节点到其他节点距离信息更新S集合和T集合分类是否包含所有集合算法结束，返回图5-1 改进的Dijkstra

43、算法流程图5.2 改进的Dijkstra算法在最优配送路线确定中的实例为了更好的说明问题，我们选取一个如图5-2 所示的简单联通区域为例，进行分析和说明具体的方案设计我们可以看到途中一共有七个配送节点，节点之间的路ABCDEFG81361531106798线权值表明的是两个节点的运输距离图5-2 路线无向有权示意图人力成本和油耗成本列表如表5-1所示，单位为千元/公里吨表5-1 人力成本表人力成本油耗成本0.350.340.370.170.420.310.380.330.790.260.510.390.350.39各个节点间的联通情况以及运输距离情况也可以列出表格如表 5-2 所示表5-2 运

44、输距离表080601530131100760890我们根据以上公式对本例中的配送节点间综合代价进行计算得到了各个配送节点间的综合权值如图5-3 所示：ABCDEFG0.722.080.661.830.380.181.791.181.111.481.36图5-3 节点间的综合权值 5.2.1 路径优化结果继而我们根据上述数据，应用 Dijkstra 算法对其进行最优配送路径确定，我们确定选定的最终结果如表5-3 所示：表5-3 路径选择图路径选择花费代价0.720.661.040.842.022.201.381.761.562.742.920.380.181.361.540.561.111.92

45、1.181.361.48这样，我们就确定了从任意一个节点出发，配送到区域内其他节点应选择的路线，以及相应的成本分析，从而可以根据这些信息调配相应的人力和车辆等资源，进行配送安排结 论本文基于Dijkstra算法，针对Dijkstra算法在实际应用中搜索速度慢，搜索效率低，时间花费多的的缺陷，对其进行了优化优化算法只对最短路径上节点的邻居做处理，而不涉及到其他节点，每个搜索过程不必全部遍历或者较少地遍历临时标记点，既缩小了搜索范围，又保证了遍历搜索的搜索成功率，从而提高了搜索效率，节省了时间，适应网络拓扑的变化，性能稳定但针对实际问题，例如物流问题，路径最短并不一定是是花销最小，相对于这一Dijkstra算法或改进算法，并不是特别理想，只能在一定程度或者范围内起到优化和改进的目的即使如此，Dijkstra算法还是