【基于Dijkstra算法的最短路径规划算法分析5700字】

基于Dijkstra算法的最短路径规划算法分析目录TOC\o"1-3"\h\u17932基于Dijkstra算法的最短路径规划算法分析 1129371.1三种最短路径算法的比较与选择 291761.2Dijkstra算法 2112751.2.1Dijkstra算法的原理 2158091.2.2Dijkstra算法的实现 534871.3Dijkstra算法在GPS导航中的实现 6172071.3.1Dijkstra算法实现步骤 6220891.3.2问题分析 7223261.3.3实验过程与结果 8258451.3.4实验分析 1034121.3.5结语 11最短路径算法是图论中的一个典型的问题.对于它的研究早在上个世纪五十年代就已经开始，保守估计至今也要有二千多篇技术文章供讨论，对最优路径的至今都没有停止过，所谓的最优路径不仅仅是地理上的距离最短，还可以使用其他的度量标准，比如最短时间，最少费用等等，以便满足不同的用户需求，但是无论是最快路径，最短时间还是最少费用，他们的核心还是最优路径算法选取的计算类型不同，比如最短时间路径算法，在计算时会首先高速公路，因为高速公路会用时最短，最少费用路径算法，在计算时会避开收费公路，这样在整个路径计算的结果中，收费公路所占比例就会降低，因此产生的过路费也就会降低.目前道路搜索优化算法以及最佳路线问题的解决方法至少有几十个方案.其中包括动态道路规划方法，神经元搜索网格，Dijkstra以及A-Star等，其中Dijkstra被GPS导航系统普遍采用，其主要思想是从近到远加入权值的搜索方式，从而找到最佳的路线方案，直达目标终点.对于已定的求解要求，我们一般会发现解决此问题会有许多的可能解决方案，因而在具体的实现中有许多问题需要探讨.需要反复不停的扫描网络中的各个节点.尝试找到在已经给定的某一节点到正在搜索的节点之间的最佳有效的路径，同时对已经扫描过的节点做标记.但目前这些算法都只是仅仅给出到达目标的路线，都普遍缺少智能特点，不能具体根据实际的路况进行计算和分析以便迅速得到一个最佳最快的路线.1.1三种最短路径算法的比较与选择导航功能中最核心的算法就是最短路径选择算法，对常见的三种最短路径算法进行分析和比较，归纳出这三种最短路径算法的对比如表3所示.表3-1三种最短路径算法对比表Floyd算法Bellman-Ford算法Dijkstra算法能否处理有向图能能能完全或单源最短路完全最短路单源最短路单源最短路能否处理负权边否能否图的存储方式邻接矩阵邻接表邻接表接表时间复杂度O(V3)O(V*E)O(E+V*log|V|)空间复杂度O(V3)O(V+E)O(V+E)根据对比可以看出，Dijkstra算法在时间和空间上都是优于Floyd算法和Bellman-Ford算法的.不足之处就是Dijkstra算法不能处理含负权边的图.但根据本系统的实际情况，地图中的道路长度一定为正数，最短行驶时间也一定为正数，所以对于Dijkstra算法的这个缺陷可以忽略不计.因此，选用Dijkstra算法来计算GPS导航功能中的最短路径问题.1.2Dijkstra算法Dijkstra算法（Dijkstra'salgorithm）是由艾兹赫尔·戴克斯特拉（EdsgerWybeDijkstra）一位荷兰计算机科学家发明的[10].该算法主要是用来解决有向图中指定的一个源点到其他顶点的最短路径问题.打比方来说一个有向图中的顶点表示一个城市，而图边上的权重值则表示城市之间开车行经的距离，该算法被用来找到两个城市之间的最短路径.1.2.1Dijkstra算法的原理Dijkstra核心算法的原理是把整个搜索路径看成是一棵树，这棵树是以某个指定起点作为其根，每个节点到这个根的搜索路径称为到这个节点的最短路径，在运用Dijkstra算法求最短路径树的时候，因为在运用算法的网络中不存在负权的问题，所以在路径树产生的过程中对各节点到指定起点的距离和点与点之间的关系会一步一步加入到树中.Dijkstra算法是有效的解决点与点之间最短距离的算法，该算法的原理是从固定的节点开始，一个节点接着一个节点的前进，每前进一个节点都要找出与原来固定起点的最短路径，一直把所有节点到原固定节点的最短路径找完.这个算法的优点是只要每个最短路径的值非负，那就一定可以找出固定节点到各个节点的最短路径.但其缺点是要查询计算所有的节点，比较浪费时间.假如找到了两个点之间的最短路径，那就没必要再去继续计算其他各点之间的距离，因为现在改进后的算法，只要找到目的节点到指定起点之间的最短路径就会结束停止计算.下面我们对该算法的基本思想进行描述，在一个给定的带权有向图G=(V,E)中用V表示节点集，其含有n个节点.E代表弧集，其包含有m条弧.而E中从vi到vj的弧用(vi,vj)表示.而弧(vi,vj)的非负权值则用h(vi,v,（3-1）在一个带权的有向图中求取最短路径其实就是计算从一个指定的起点到一个固定的权值最小的路径，假如用弧的长度表示权值的话，那最小路径就是从起点到终点的最小弧长度之和.为了进一步说明迪科斯彻算法的原理，我们可以从单源点的角度进行分析.在一个给定了起点P的带权有向图G=(V,E)中计算起点P到V中包含的其他节点的最短距离.对于这样的问题，Dijkstra算法提出了一种按路径长度增长顺序来计算最短路径的方法.用举例说明，以D为开头，求D到各个点的最短距离.图3-1有权图第1步：初始化距离，其实指与D直接连接的点的距离.dis[C]代表D到C点的最短距离，因而初始dis[C]=3，dis[E]=4，dis[D]=0，其余为无穷大.设置集合S用来表示已经找到的最短路径.此时，S={D}.现在得到D到各点距离{D(0)，C(3)，E（4），F（∗），G（∗），B（∗），A(∗)}，其中*代表未知数也可以说是无穷大，括号里面的数值代表D第2步：不考虑集合S中的值，因为dis[C]=3，是当中距离最短的，所以此时更新S，S={D,C}.接着我们看与C连接的点，分别有B，E，F，已经在集合S中的不看，dis[C−B]=10，因而dis[B]=dis[C]+10=13，dis[F]=dis[C]+dis[C−F]=9，dis[E]=dis[C]+dis[C−E]=3+5=8>4(初始化时的dis[E]=4)不更新.此时{D(0)，C(3)，E（4），F（9），G（*），B（13），A(*)}.第3步：在第2步中，E点的值4最小，更新S={D，C，E}，此时看与E点直接连接的点，分别有F，G.dis[F]=dis[E]+dis[E−F]=4+2=6（比原来的值小，得到更新），dis[G]=dis[E]+dis[E−G]=4+8=12（更新）.此时{D(0)，C(3)，E（4），F（6），G（12），B（13），A(∗)}.第4步：在第3步中，F点的值6最小，更新S={D，C，E，F}，此时看与F点直接连接的点，分别有B,A,G.dis[B]=dis[F]+dis[F−B]=6+7=13，dis[A]=dis[F]+dis[F−A]=6+16=22，dis[G]=dis[F]+dis[F−G]=6+9=15>12（不更新）.此时{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.第5步：在第4步中，G点的值12最小，更新S={D，C，E，F，G}，此时看与G点直接连接的点，只有A.dis[A]=dis[G]+dis[G−A]=12+14=26>22(不更新).{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.第6步：在第5步中，B点的值13最小，更新S={D，C，E，F，G，B}，此时看与B点直接连接的点，只有A.dis[A]=dis[B]+dis[B−A]=13+12=25>22(不更新).{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.第6步：最后只剩下A值，直接进入集合S={D，C，E，F，G，B，A}，此时所有的点都已经遍历结束，得到最终结果{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.1.2.2Dijkstra算法的实现前面经过对算法思想和原理的分析，我们可以采用邻接节点法来实现，其基本思想为先找出道路网中每个节点与其直接相连的节点的个数也称为最大邻接点，使用maximum来表示最大邻接点并将其作为矩阵的列数.一个道路网络矩阵的行数由其节点总数N来表示，道路网络中节点与节点之间的邻接关系用邻节点矩阵J来表示，J的行号是由节点的号顺序排列的，凡是与节点vi相邻的节点都填充到矩阵的第i行.假如其相邻的节点数小于最大邻接数maximum则使用0来填充第i行，一直到填满.使用Dj来表示初始判断矩阵，其构造的方法与J相同，凡是与J中的每一个节点有邻接关系的对应边，其对应的权值填在同一位置上（其中∞表示0元素)，这样的话J(vi,vj为了有效的能求解指定两个节点之间的最短路径,为了能够获取初始化的矩阵J以及Dj1，首先加载道路地图数据，得到地图数据中所有节点的序列号.需要注意的是电子地图数据中的点与线的序号可能与实际的编号有差异，为了提高算法的灵活性这里统一使用地图网络数据中的序号作为参数进行运算.2，获取地图网络数据的最大邻接节点数值（maximum).3，构造并初始化邻接节点矩阵J，每一行的节点序列号可以任意放置，参照矩阵J的元素来构造判断矩阵Dj.完成矩阵J和D步骤1，用向量Flag(vi)来作为初始标记.Flag(步骤2，以起点v0为基础初始化判断矩阵Dj，第v0行的元素值，其中Flag(步骤3，以终点vn为判断依据，判断是否已经标注Dj的第步骤4，在判断矩阵Dj中那些已经被标记过的行中，把每一元素的最小值求出并用Lmin表示.假如Lmin=∞则说明根本不存在最短距离，则程序直接退出.否则就是存在最短距离mindist=Lmin,把最小值所在的vi行和vj列记录下来并在矩阵J中取出(vi,vj)的元素值，并用变量W记录.假如第W行没有被标记则去标记判断矩阵Dj对应的W行，同时把vi赋值给Flag(W)，同时在矩阵J中去查找对应W行的值为vi的元素，并用ri和步骤5，知道起点S和终点D，从终点开始沿着被标记的Flag的分量向前查询，得到的mindist即为最短路径.1.3Dijkstra算法在GPS导航中的实现1.3.1Dijkstra算法实现步骤目前求最短路径问题的方法中比较有优势的是Dijkstra算法，且在交通网络最短路径中也展现了它的优势.故本文在改进Dijkstra算法的基础上运用Matlab程序代码依次求出局部最优解，然后整合得到全局最优路径，并以上海吴泾镇到延安西路900号的驾驶路线为例，结合不同需求对交通线路进行优化设计.把Dijkstra算法节点分为临时标记节点，未标记节点和永久标记节点.Dijkstra的原始版本找到两个顶点之间的最短路径，但更常见的特定一个顶点，作为源节点然后找到该顶点到图中所有其他节点的最短路径，产生一个最短路径图.首先把路线图画为有权重的有向图G，以及G中的一个来源顶点v0.我们用V表示G中所有的顶点的集合.图中的边都是两个顶点形成的有序元素对.(vi，vj)表示从顶点vi到vj有路径相连，E表示G中所有边的集合，而边的权重则由权重函数定义.因此，就是从顶点到顶点的非负权重.边的权重可以想象成两个顶点之间的距离.任两点间路径的权重，就是该路径上所有边的权重总和.已知集合中有源点及改进Dijkstra算法可以找到的最低权重路径.每两条主干路的交汇路口组成的集合为V，进一步找到最短路径的顶点放到新的集合中V’，初始状态时，集合V'1.3.2问题分析（一）问题提出从上海郊区吴泾镇到达延安西路900号参加考试，本身半小时不到的路程在早高峰时间如若选择不好交通道路，可能驾驶路程时间会在2小时以上，有很多驾驶员会在距离短拥堵多和距离长拥堵少两种情况中纠结选择.现在假定不出现车辆故障和交通事故，考虑以下两个问题.从早上7点45分出发，吴泾镇开往延安西路900号路线最短、时间最短的路线设计.（二）符号说明1：起点吴泾镇2：龙吴路与龙耀路交叉路口3：龙吴路/龙华西路路口4：红梅高架路出口5：中环路/虹许路路口6：沪闵高架路/内环高架路7：沪闵高架路/漕溪北路路口8：龙华西路/中山南二路路口9：龙耀路与云锦路交叉路口10：康平路/华山路路口11：延安高架路入口12：延安西路900号（三）数据来源根据早高峰时间选择路线，通过网络查询得到各个线路之间的距离、路途消耗时间[12].实验环境软件版本：matlabr2016a1.3.3实验过程与结果由图1可以抽象出图2图1图2图2可以抽象出来两个矩阵，用矩阵来表示图，图的表示方式为：矩阵中的元素A（i，j）表示i点与j点所相接的边的权重，如果i与j没有直接相接的边的话，权重为无穷大，在这里表示成2147483647，自身到自身的权重是0.Eg：A（4,6）=6.5km，A（2,9）=3.2A（4,8）=A（3,3）=0最终会将图2抽象成两个矩阵，一个用来存储时间的权重，另一个用来储存距离的权重，分别为图3和图4.。。。。。。。。。。。。。。。。。。。。图3距离的权重图图4时间的权重图Dijkstra算法表示的是单源最短路径，我这里把1作为起点得到的结果如下:图5距离图的结果第一行表示的是起点到每个点的最短距离，得到1到2的最小距离为13km,1到3的最小距离是15，这里可以得到1到12的最小距离是22.8.第二行表示的储存的路径的最终点到起始点1的上一个点是哪一个点，比如1到12之间最短路径是12-10-7-8-3-1.具体看的方法如下：从12开始，看第二行的数据，12的第二行是10就表示上一个点是10，找到10之后再看10的第二行，可以找到第上一个点是7，以此类推，直到第二行的数据是1为止，就可以得到一条最短路径.图6时间图的结果和距离图的使用方式一样，只是从最短距离换成了最短时间.得出最短路程路线：1-3-8-7-10-12，该线路行程共22.8km.最省时间路线：1-4-7-10-12，该线路途中用时85mins.1.3.4实验分析结合实际的交通状态进行分析，起点和目的地之间的道路处于通畅状态，因此最短路径就处于虹梅高架路以及中环路的主干道上.而在早高峰时段，主干道交通拥挤，此时需要尽可能避开拥堵路段，选择车流量较少路况较通畅的路段.同一条道路选择下，车辆在平时段和高峰时段时长要平均相差70分钟，在Dijkstra算法下不同路径选择可以节约20分钟的时间，这说明此算法的应用具有可行性，路径选择结果符合实际交通状况，可以帮助更好优化路线，满足实际出行的需要.Dijkstra函数代码如下：%n为方阵维度%x为起始点%input为输入的图，output为输出结果的路径function[output]=dijkstra(input,n,x)%各个变量的初始化output=zeros(2,n);%输出的初始化.输出的第一层是距离，第二层是路径tag=zeros(1,n);%用于标记被使用过的顶点count=n-1;%用于记录仍然未被使用的顶点，除了起始点以外，初值为n-1dist=zeros(1,n);path=zeros(1,n);distcap=2147483647;%定义int32最大值为无穷距离%对路径以及最短距离的初始化fori=1:ndist(1,i)=distcap;%取int32最大值表示无穷距离path(1,i)=-1;%-1表示未找到路径end%找到与初始点邻接的顶点，更新最短距离与路径的值fori=1:nifinput(x,i)<dist(1,i)dist(1,i)=input(x,i);path(1,i)=x;tag(1,x)=1;endend%dijkstra算法的实现while1distmin=distcap;%用于储存dist中找到的最短距离的值,初值为无限大fori=1:nifdist(