几种常用的最短路径算法

1、简述几种常用的最短路径算法摘要：随着社会的发展，最短路径问题在现实生活中占据的地位越来越重要。求解这一类问题的方法有很多，包括Floyd算法、Dijkstra算法、Bellman-Ford算法、动态规划算法和智能优化算法。其中较为常用的 是Floyd算法、Dijkstra算法和Bellman-Ford算法。本文将简单介绍这三种最短路径算法，通过比较各种方 法的优劣使对其有更进一步的认识和学习。关键字：最短路径；最短路径算法； Floyd算法；Dijkstra算法；Bellman-Ford算法随着计算机科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为计算机 科学、运筹学、地理信息科学

2、等学科的一个研究热点。 也正因为最短路径问题在实际生产生 活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。y1 .最短路径概述最短路径问题是指在一个赋权图的两个节点之间找出一条具有最小权的路径，这是图论的描述，也是图论中研究的一个重要问题。现实生活中我们可以看到这些最短路径问题的例 子，公交车辆的最优行驶路线和旅游线路的选择等；军事领域中也有应用，作战部队的行军 路线等问题就与寻找一个图的最短路径密切相关，因此对最短路径问题的深入研究和广泛应 用具有重要意义和实用价值。在线路优化问题中，如果优化指标与路程的相关性较强，而和其他因素相关性较弱时， 即以最短路程为准则，则考虑转化为

3、最短路径问题。比如军事行军线路选取时，假如从出发 地到目的地之间有多种线路可以选取，危险指数在预测概率相等时，就要考虑最短路径问题。2 .最短路径算法概述最短路径算法问题是图论研究中的一个经典算法问题，旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题 -即已知起始结点，求最短路径的问题。确定终点的最短路径问题 -与确定起点的问题相反，该问题是已知终结结点，求最短 路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。全

4、局最短路径问题 -求图中所有的最短路径。3 .Floyd 算法3.1 算法定义Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最 短路径问题，同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为 O(N3),空间复杂度为O(N2)。3.2 算法描述3.2.1 算法思想原理Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是 寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个 诠释。从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j, 2是从i经过若干个节点k到j。所以，我们假设 D

5、is(i,j)为节点u到节点v的最短路径的距离，对于每 一个节点k,我们检查 Dis(i,k) + Dis(k,j) < Dis(i,j) 是否成立，如果成立，证明从 i到k再到j 的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍 历完所有节点k, Dis(i,j)中记录的便是i至ij j的最短路径的距离。3.2.2 算法过程描述a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。b.对于每一顶点u和v,看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。3

6、.3 算法适用范围(lAPSP(All Pairs Shortest Paths);(2稠密图效果最佳；(3边权可正可负。3.4 算法实例根据图1,用Floyd算法找出任意两点的最短路径步骤如下表1:表1 Floyd算法步骤流程distk1distk2distk3MINA->B1371A->C135*1A->D3353B->C2262B->D*44*4C->D24624 .Dijkstra 算法4.1 算法定义Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到

7、终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。问题描述：在无向图G=（V,E）中，假设每条边 Ei的长度为 wi,找到由顶点 V0到 其余各点的最短路径。4.2 算法描述4.2.1 算法思想原理设G=（V,E）是一个带权有向图，把图中顶点集合 V分成两组，第一组为已求出最短路径的顶点集合（用 S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用 U表示），按最短路径长度的递

8、增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从 v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括 S中的顶点为中间顶点的当前最 短路径长度。4.2.2 算法过程描述a.初始时，S只包含源点，即$=口,丫的距离为0o U包含除v外的其他顶点，即:U=其 余顶点,若v与U中顶点u有边，则5丫正常有权值，若u不是v的出边邻接点，则5丫 权值为8。b.从U中选取一个距离 v最小的顶点k,把k,加入S中（该选定的距离就是 v到k的 最短路径长度）。c.

9、以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过 顶点k）比原来距离（不经过顶点k）短，则修改顶点 u的距离值，修改后的距离值的顶点k的距离加上边上的权。d.重复步骤b和c直到所有顶点都包含在 S中。 4.3算法适用范围（1单源最短路径；（2有向图和无向图；（3所有边权非负。 4.4算法实例71/ 图2无向图根据图2,用Dijkstra算法找出以A为起点的单源最短路径步骤如下表2：表2 Dijkstra算法步骤流程步骤S集合中U集合中1选入A ,此时S =A此时最短路径A->A =0以A为中间点，从A开始找。U = B, C, D, E, FA->B =

10、2 , A->C = 1A->U中其他顶点 =8其中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八） 不替换B的权值A->C->D = 4A->C->E = 2A->C->U中其他顶点 =8 其中 A->B = 2 和 A->C->E=2 为取短3选入B,

11、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中其他顶点 =8其中 A->C->E->D = 34选入 D,

12、此时 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 这条最短路 径开始新一轮查找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

13、 = 0,A->C = 1 , A->B = 2 , A->C->E=2 ,A->C->E->D=3,A->C->E->F = 4U集合已空，查找完毕5.Bellman-Ford 算法5.1 算法定义Bellman-Ford算法-能在更普遍的情况下（存在负权边）解决单源点最短路径问题。不 允许边的权是负权，如果遇到负权，则可以采用Bellman-Ford算法.算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的 点进行松弛，若某个相邻的点松弛成功，则将其入队，直到队列为空时算法结束。 5

14、.2算法描述 5.2.1算法思想原理Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于 给定的带权（有向或无向）图 G= （V,E）,其源点为s,加权函数 w是边集E的映射。对 图G运彳B Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d&#91;v&#93;5.2 .2算法过程描述a.初始化：将除源点外的所有顶点的最短距离估计值d&#91;v&#93;+oo,d&#91;s&#93;0;b.迭

15、代求解：反复对边集E中的每条边进行松弛操作，使得顶点集 V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）c.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false,表明问题无解；否则算法返回true,并且从源点可达的顶点v的最短距离保存在 d&#91;v&#93;中。 5.3算法适用范围（1单源最短路径；（2有向图和无向图；边权可正可负；（4差分约束系统。5.4算法实例图3无向图根据图3,用Bellman-Ford算法找出以a为起点的单源最短路径步骤如下表3:表3 Bellman-Ford算法步骤流程kdist

16、kadistkbdistkcdistkddistkedistkf10251*202412103023124402312450231246 .几种算法的比较Floyd算法适用于是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单 有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。其优点是容易理解，可以算出任意两个节点之间的最短距离，代码编写简单 。但是时间复杂度比较 高，不适合计算大量数据。Dijkstra(迪杰斯特拉)算法是一种按路径长度递增的次序产生最短路径的算法，可求单 源、无负权的最短路。 其适用于有向图及无向图，时效性较好，时间复杂度为O (V

17、*V+E ),可以用优先队列进行优化，优化后时间复杂度变为0 (v*lgn)。但是由于其遍历计算的节点很多，所以算法的效率较低。Bellman-Ford算法是求解单源最短路问题的一种算法，可以判断有无负权回路(若有, 则不存在最短路)，时效性较好，时间复杂度 O (VE)。与Dijkstra算法不同的是，在 Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路(即从v出发，经过若干个点之后又回到v)且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去，而Bellman-Ford算法具有分辨这种负环路的能力。7 .总结Floyd算法、Dijkstra算法和Bellman-Ford算法是目前的最短路径算法中较为常用的三个算法。每种