基于dijkstra的最短路径搜索算法的优化及应用—毕业设计论文

基于dijkstra的最短路径搜索算法的优化及应用—毕业设计论文内容摘要：

为距离 4+边 2,4 的长度 距离 2,所以不更新 ) 医院 1 已 标号 距离 0 医院 2 未标号 距离 ∞ 医院 3 已 标号 距离 4 医院 4 未标号 距离 9 12 4 5 6 医院 1 已 标号 距离 0 医院 2 未标号 距离 ∞ 医院 3 未标号 距离 4 医院 4 未标号 距离 ∞ 12 4 5 6 10 找所 有未标号中距离最短的顶点为 医院 2,将 2做标号 ,已没有与 2相邻的未标号顶点需要更新了 再次找所有未标号中距离最短的顶点已找不到 ,得结果 d(2)=12,d(3)=4,d(4)=9. Dijkstra算法的优缺点 Dijkstra 算法能够保证 100%找到最优解，但其搜索速度较慢，搜索效率非常低，时间花费较多，一般只能用于离线的路径规划问题。 如节点数为 n的图，用 Dijkstra算法计算最短路径总共需要迭代 n一 1次，每次迭代都新加一个节点到临时节点集合中 ，由于第 i次迭代时不在临时节点集合中的节医院 1 已 标号 距离 0 医院 2 已 标号 距离 ∞ 医院 3 已 标号 距离 4 医院 4 已 标号 距离 9 12 4 5 6 医院 1 已 标号 距离 0 医院 2 未标号 距离 12 医院 3 已 标号 距离 4 医院 4 以 标号 距离 9 12 4 5 6 11 点 数为 ni．即第 i次迭代需对 ni个节点进行处理，因此其所需的处理数为11( 1)() 2ninnni ，对 n个节点网络的时间复杂度是 O(n2)。 在实际应用当中，使用 Dijkstra算法查找最短路径时耗费大量的时间进行数据的比较，本文对 Dijkstra算法进行分析，通过改变算法实现减少不必要节点计算的时间，提高算法的效率达到对其进行优化。 下一个例子说明 Dijkstra算法存在的缺陷： 例：图 G(V， E， W)，求从 v1出发到其 它各个顶点的最短路径长度。 图 权图 G 解： wi表示由源 v1到点 vi的最短距离； S表示已求出最短路径的顶点集合，其初始值为 S{v1}； k表示刚选出的顶点的编号；选出 vk后修改 U中各顶点的距离的方法为：wi=min{wi， dki}； 下表通过 Dijkstra算法来求解图 ： v1 初始 第一步 第二步 第三步 … v2 15 9 v3 ∞ ∞ v4 4 v5 ∞ ∞ v6 ∞ 10 v7 ∞ ∞ S={v1} v4 v2 k 12 w S v1,v4 v1,v2,v4 在上表中选出顶点 v4加入到 S时一共进行了 6次比较，其中四次是与 ∞作比较，也就是说这四次完全没有必要进行比较。 当选出 v4后，需要对 U中的各个顶点的距离进行调整，在调整过程中利用到 wi =min{wi， w4+d4i}其中 i≠1， 4(1， 4已经在 S中 )即需要对 wi和 w4+d4i进行比较，但我们在对 w3,w5,w7进行调整时可以发现由于 d43，d45， d47 ∉ E(G)即它们的权值为 ∞，所以调整时是没有必要进行 比较的，在这里多进行了 3次比较。 后面的各步也都出现类似的情况 (后略 )，尤其是当图的边数相对较少时更为明显。 以 Dijkstra 算法为基础算法进行优化的原因 Dijkstra算法与其他主流算法的比较 [5] 搜索速度比较 对 5张图分别采用 Dijkstra算法、 A*算法、遗传算法进行路径规划，他们各自花费的时间如表。 表 三种算法在搜索速度上的对比 节点数 搜索速度 Dijkstra算法 A*算法 遗传算法 16 1 1 2 32 4 2 4 43 7 3 6 62 15 5 9 78 25 7 12 由表 ：当地图节点个数和弧的条数比较少时，三种算法所花费的时间差不多，当节点个数和弧的条数比较多时， A*算法最快，遗传算法其次，Dijkstra算法最慢，而且这种差距将随节点和弧数量的增加而变得更加明显。 对于实际地图而言，由于节点与道路的数量一般都很的大， Dijkstra算法在搜索速度方 13 面弱势明显。 搜索成功率比较 对于具有 n个节点的地图，其待规划节点的个数为 n1（除起点节点外，其他均可作为待规划节点），由于每个待规划节点对应于一条最短路径，所以对每张具有n个节点的 地图而言，应该规划出 n1条最短路径。 对 5张地图分别采用三种算法进行路径规划，三者各自搜索到最短路径的情况如表。 表中括号外数据为各算法实际得到最短路径数，括号内数据则为各算法实际得到路径数和应该规划出的最短路径数 n1之比。 表 三种算法在搜索质量方面的对比 节点数 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%) 由表 ：当地图节点个数和弧数量比较多时， Dijkstra算法是一种遍历算法，每次能保证 100%搜索到最短路径，遗传算法搜索到最短路径的成功率比Dijkstra算法低一些， A*算法最低，且这种差距在节点数和弧数量越大时更加明显。 14 第 3章 Dijkstra优化算法研究 多种 Dijkstra 优化算法的研究 [6] 第一类优化算法 ——减小算法中成功搜索的搜索范围 减小算法中成功搜索的搜索范围以尽 快到达目标节点。 在对现实问题中的交通图初始化为网络拓扑图时，虽然终点已知，而源点 尚未确定，但依据常识离案发地段最近的派出所应为案发地段所在辖区 派出所，或其周边派出所，也就是源点的选取范围可以确定。 利用 MapObjects2组件提供 的 (expression)记录集筛选方法，根据案发地段 (终点 )的不同，动态选取案发地段所在辖区及相邻辖区的道路图层及派出所图层数据进行最短路径查询，从而有效地减少了拓扑图中节点总数 n的值。 第二类优化算法 ——改进算法的存储结构 在实际工作中，还要建立起空间数据结构。 网络数据结构使用的是 ―边和节点 ‖的数据结构，该数据结构是建立在图论的基础上，节点可用来定义边的连接关系。 对于网络数据的存储，传统的是采用图论中的邻接矩阵方法，其存储量为 N N(N为网络中节点数 )。 通常的地理网络，尽管节点很多，但与节点相关联的节点数目并不多，一般都为稀疏图，将会浪费大量的空间。 若采用邻接表的链式存储结构，其存储量为 E(E为节点列表中，同节点关联的所有边的数目 )，可节省大量的存储空间，尤其是在表示与节点和边相关信息较多的地理网络时，更为有效。 但邻接表却难 以判断两节点之间的关系，因此本文提出利用。 NET框架提供的特殊类Hashtable。 .NET框架包含特殊类，比如通常所说的集合类用于存储对象。 与数组类似，集合类可以把对象放入容器中，然后再取出．但集合的使用方法与数组不同，拥有用于插入和删除项的专用方法。 使用 Hashtable最大的优点就是大大降低数据存储和查找的时间花费，几乎可看成是常数时间。 15 本文对 Dijkstra 优化算法的研究 本文采用第一类优化算法减小搜索范围的思路对 Dijkstra算法进行优化。 优化算法的目标 Dijkstra算法用来求解图上从任 一节点 (源点 )到其余各节点的最短路径。 其时间复杂度为 O(N2)；采用邻接矩阵存储网络拓扑结构，需要 (NN)的存储空间，随着节点数 N的增大，其计算效率和存储效率越低。 针对此问题，提出了 Dijkstra算法的改进，本文在对传统 Dijkstra算法分析的基础上，对其进行了优化，优化算法只对最短路径上节点的邻居做处理，而不涉及到其他节点。 优化算法思路 Dijkstra算法基本方法：设 wj是从源点 s到节点 j的最短路径长度； pj是从 s到 j的最短路径中 j点的前一节点。 S是标识集合； T是未标识集合； M是节点集合． dij提节点 i到节点 j的距离 (i与 j直接相连，否则 dij = ∞)．算法步骤如下： Step0： S = {s}； T = MS； wj = dij(j∈ T， s与 j直接相连 )或 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}； j∈ T pi =s。 Step2：修改 T中 j节点的 wj值： wj = min(wj,wi + dij)；若 wj值改变，则 pj = i． j∈ T i∈ S Step3：选定所有的 wj最小值，并将其划归到 S中： wi = min wj； S=S∪ {i}； T=T{i}；若 │S│= n, 所有节点已标识，则算法终 j∈ T 止，否则，转人 Step2。 通过分析传统 Dijkstra算法的基本思路，传统 Dijkstra算法存在如下两点不足： 16 (1)当从未标记节点集合 T中选定一个节点 k作为转接点后时，需扫描未标记节点集合 T中的节点 j并更新其 wj值，而未标记节点集合 T中往往包含 大量与转接节点 k 不直接相连的节点 i(即 dki = ∞)； (2)在未标记节点集合 T中选择一个 w值最小的节点作为下一个转接节点，然而下一个转接节点往往是与标记节点集合 S中的节点直接相连的。 优化算法描述 基于上述两点不足，对传统 Dijkstra算法进行优化，算法优化思路为：首先从源点 s的邻居集合 NBS(与 s直接相连的节点集合 )中选择距离最小的邻居节点 k作为转接点，同时将划归到标识集合 S(初始时， S为 {s})。 然后对 k邻居集合与标识集合的差集 (NBk S)中节点的值进行更新，从标识集合 s中所有节点的邻居集合 的并集与标识集合的差集 (∪ NBs S， i∈ S)中选择一个 wk值最小的节点作为下一个转接点，并划归到标识集合 S中。 重复上述过程，直到所有的节点都被标识过，即 │S│=n，算法结束。 设 NBi为节点 i的邻居集合； S为标识集合； wj是从源点 s到节点 j的最短路径长度； pj是从 s到 j的最短路径中 j点的前一节点； dij是节点 i到节点 j的距离。 算法步骤如下： Step0：初始化 S = {s}； wi = dsi(i∈ NBs)；否则 = ∞(I ∉ NBs)； pi=s。 Step1：若 dsk = min dsj ，则 S = S ∪ { k}。 j∈ NBs Step2：修改 NBk S中的 wj值： wj = min { wj,wk +dkj }；若 wj值改变，则 pj = k。 j∈ NBs S Step3：选定 NBi S(i∈ S)中的 wj最小值，并将其划归到 s中： wk = min wj； S = S ∪ {k}；若 │s│= n；所有节点已标识，则算法终止， j∈∪ NBs–S i∈ S 否则，转到 Step2． 图 G7，对 G7分别用 Dijkstra算法和优化了的 Dijkstra算法进行求解，则可得从 v1到其余各节点的最短路径。 17 图 非负权值图 经典 Dijkstra算法求解过程： Step0：初始化 S = (v1)， w1 = 0， T = (v2,v4, v3,v5, v6,v7)； Step1： w4 = d14 = mind1j = 2（ d12 = d14，任选其一，本文选 v4）， S = (v1,v4)， T = j∈ T (v2,v3,v5,v6,v7)； Step2： T = (v2,v3,v5,v6,v7) w2 = min{w2， w4 + d42}= min{2， 4}= 2， w3 = min{w3， w4 + d43}= min{5,5} = 5 2 = w2， w5 = min{w5， w4 + d45} = {∞， 3} = 3 2 = w2， w6 = min{w6， w4 + d46} = ∞， () w7 = min{w7， w4 + d47} = ∞，。