《几种常用的最短路径算法》由会员分享，可在线阅读，更多相关《几种常用的最短路径算法（6页珍藏版）》请在金锄头文库上搜索。
1、随着计算机科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正因为最短路径问题在实际生产生活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。1. 最短路径概述最短路径问题是指在一个赋权图的两个节点之间找出一条具有最小权的路径，这是图论的描述，也是图论中研究的一个重要问题。现实生活中我们可以看到这些最短路径问题的例子，公交车辆的最优行驶路线和旅游线路的选择等；军事领域中也有应用，作战部队的行军路线等问题就与寻找一个图的最短路径密切相关，因此对最短路径问题的深入研究和广泛应用具有重要意义和实用价值。在线路优化问题中，如
2、果优化指标与路程的相关性较强，而和其他因素相关性较弱时,即以最短路程为准则，则考虑转化为最短路径问题。比如军事行军线路选取时，假如从出发地到目的地之间有多种线路可以选取,危险指数在预测概率相等时，就要考虑最短路径问题。2. 最短路径算法概述最短路径算法问题是图论研究中的一个经典算法问题，旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题-即已知起始结点，求最短路径的问题。确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点
3、的问题。确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。全局最短路径问题-求图中所有的最短路径。Floyd算法3.1算法定义Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(N3),空间复杂度为O(N2)。3.2算法描述3.2.1算法思想原理Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释。从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i
4、到j,2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k)+Dis(k,j)B1371A-C135*1A-D3353B-C2262B-D*44*4C-D2462Dijkstra算法4.1算法定义Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。问题描述
5、：在无向图G=(V,E)中，假设每条边Ei的长度为wi,找到由顶点V0到其余各点的最短路径。4.2算法描述4.2.1算法思想原理设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此
6、顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。4.2.2算法过程描述a. 初始化SPT顶点集S=v,v的距离为0。sU包含除v外的其他顶点，即:U=其余顶点,若v与U中顶点u有边，则vu,v正常有权值，若u不是v的出边邻接点，则vu,v权值为3。b. 从U中选取一个距离v最小的顶点k,把k,加入S中（该选定的距离就是v到k的最短路径长度）。c. 以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。d. 重复步骤b和c直到
7、所有顶点都包含在S中。4.3算法适用范围单源最短路径；有向图和无向图；所有边权非负。4.4算法实例图2无向图根据图2,用Dijkstra算法找出以A为起点的单源最短路径步骤如下表2：,表2Diikstra算法步骤流程，步骤S集合中U集合中1选入A,此时S=A此时最短路径A-A=0以A为中间点，从A开始找。U=B,C,D,E,FA-B=2,A-C=1A-U中其他顶点=3其中A-C=1权值最小，路径最短2选入上一轮中找到的最短路径的顶点C,此时S=A,C此时最短路径A-A=0，A-C=1以C为中间点，从A-C=1这条最短路径开始新一轮查找U=B,D,E,FA-C-B=3（比上面的A-B=2要大）不
8、替换B的权值A-C-D=4A-C-E=2A-C-U中其他顶点=s其中A-B=2和A-C-E=2为最短3选入B,E此时S=A,C,B,E此时最短路径A-A=0，A-C=1，A-B=2A-C-E=2以B和E为中间点，从A-B=2和A-C-E=2这两条最短路径开始新一轮查找U=D,FA-B-D=5（比上面的A-C-D=4大，不替换，保持D的权值为A-C-D=4）A-C-E-D=3A-C-E-F=4A-B-U中其他顶点=s其中A-C-E-D=3最短4选入D,此时S=A,C,B,E,D此时最短路径A-A=0，A-C=1，A-B=2，A-C-E-D=3以D为中间点，从A-C-E-D=3这条最短路径开始新一
9、轮查找U=FA-C-E-D-F=8（比上面的A-C-E-F=4要长，保持F的权值为A-C-E-F=4）其中A-C-E-F=4最短5选入F,此时S=A,C,B,D,E,F此时最短路径A-A=0，A-C=1，A-B=2，A-C-E=2，A-C-E-D=3,A-C-E-F=4U集合已空，查找完毕Bellman-Ford算法5.1算法定义Bellman-Ford算法-能在更普遍的情况下（存在负权边）解决单源点最短路径问题。不允许边的权是负权，如果遇到负权，则可以采用Bellman-Ford算法.算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松
10、弛，若某个相邻的点松弛成功，则将其入队，直到队列为空时算法结束。5.2算法描述5.2.1算法思想原理Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图G=（V,E）,其源点为s,加权函数w是边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径d[v]5.2.2算法过程描述a. 初始化：将除源点外的所有顶点的最短距离估计值d[v]+叫d[s]0;b. 迭代
11、求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行lvl-1次）c. 检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在d[v]中。5.3算法适用范围单源最短路径；有向图和无向图；边权可正可负；差分约束系统。5.4算法实例图3无向图根据图3,用Bellman-Ford算法找出以a为起点的单源最短路径步骤如下表3：表3Bellman-Ford算法步骤流程kdistkadistkbdistkcdist
12、kddistkedistkf10251*20241210302312440231245023124几种算法的比较Floyd算法适用于是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行V|次Dijkstra算法。其优点是容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。但是时间复杂度比较高，不适合计算大量数据。Dijkstra(迪杰斯特拉)算法是一种按路径长度递增的次序产生最短路径的算法，可求单源、无负权的最短路。其适用于有向图及无向图，时效性较好，时间复杂度为O(V*V+E),可以用优先队列进行优化，优化后时间复杂度变为
13、0(v*lgn)。但是由于其遍历计算的节点很多，所以算法的效率较低。Bellman-Ford算法是求解单源最短路问题的一种算法，可以判断有无负权回路(若有，则不存在最短路)，时效性较好，时间复杂度O(VE)。与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路(即从v出发，经过若干个点之后又回到v)且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去，而Bellman-Ford算法具有分辨这种负环路的能力。3. 总结Floyd算法、Dijkstra算法和Bellman-Ford算法是目前的最短路径算法中较为常用的三个算法。每种算法都有其自己的特点和优势。比方说若路径规划问题较为简单，可采用Floyd算法；若路径规划问题涉及到负权边，可采用Bellman-Ford算法。总之，在实际应用中，根据路径问题的特点采用合理的路径规划算法，方能达到最优的效果。1 参考文献杨丽萍最短路径算法在校园导游系统中的应用计算机时代,2014(2)吴家琴基于迪杰斯特洛模型的物流运输最短路径的选择物
