几种常用的最短路径算法.doc

简述几种常用的最短路径算法

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

随着计算机科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正因为最短路径问题在实际生产生活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。
1.最短路径概述
最短路径问题是指在一个赋权图的两个节点之间找出一条具有最小权的路径，这是图论的描述，也是图论中研究的一个重要问题。现实生活中我们可以看到这些最短路径问题的例子，公交车辆的最优行驶路线和旅游线路的选择等；军事领域中也有应用，作战部队的行军路线等问题就与寻找一个图的最短路径密切相关，因此对最短路径问题的深入研究和广泛应用具有重要意义和实用价值。
在线路优化问题中，如果优化指标与路程的相关性较强，而和其他因素相关性较弱时，即以最短路程为准则，则考虑转化为最短路径问题。比如军事行军线路选取时，假如从出发地到目的地之间有多种线路可以选取，危险指数在预测概率相等时，就要考虑最短路径问题。
2.最短路径算法概述
最短路径算法问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：
　　确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。
　　确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题
　　确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
　　全局最短路径问题 - 求图中所有的最短路径。
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。所以，我们假设Dis(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到j的最短路径的距离。
3.2.2算法过程描述
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连则权为无穷大。 　　
b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
3.3算法适用范围
⑴APSP(All Pairs Shortest Paths)； 
⑵稠密图效果最佳； 
⑶边权可正可负。
3.4算法实例

图1 无向图
根据图1，用Floyd算法找出任意两点的最短路径步骤如下表1：
表1 Floyd算法步骤流程

distk[1]
distk[2]
distk[3]
MIN
A->B
1
3
7
1
A->C
1
3
5
*

1
A->D
3
3
5
3
B->C
2
2
6
2
B->D
*
4
4
*
4
C->D
2
4
6
2

4.Dijkstra算法
4.1算法定义
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。
4.2算法描述
4.2.1算法思想原理
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
4.2.2算法过程描述
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
4.3算法适用范围
⑴单源最短路径； 
⑵有向图和无向图；
⑶所有边权非负。
4.4算法实例

图2 无向图
根据图2，用Dijkstra算法找出以A为起点的单源最短路径步骤如下表2：
表2 Dijkstra算法步骤流程
步骤
S集合中
U集合中
1
选入A，此时S ={A}
此时最短路径A->A =0
以A为中间点，从A开始找。

U = {B, C, D, E, F}
A->B = 2，A->C = 1
A->U中其他顶点 = ∞
其中A->C = 1权值最小，路径最短

2
选入上一轮中找到的最短路径的顶点C，此时S = {A, C}
此时最短路径A->A =0，A->C = 1
以C为中间点，从A->C=1这条最短路径开始新一轮查找

U = {B, D, E, F}
A->C->B = 3(比上面的A->B = 2要大)
不替换B的权值
A->C->D = 4
A->C->E = 2
A->C->U中其他顶点 = ∞
其中A->B = 2和A->C->E=2为最短

3
选入B,E此时S = {A, C, B,E}
此时最短路径 A->A = 0，A->C = 1，A->B = 2
A->C->E=2
以B和E为中间点，从A->B = 2和A->C->E=2这两条最短路径开始新一轮查找

U = {D, F}
A->B->D = 5(比上面的A->C->-D = 4大，不替换，保持D的权值为A->C->D=4)
A->C->E->D=3
A->C->E->F=4
A->B->U中其他顶点 = ∞
其中 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这条最短路径开始新一轮查找

U = { F}
A->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 = 4

U集合已空，查找完毕

5.Bellman-Ford算法
5.1算法定义
Bellman-Ford算法--能在更普遍的情况下（存在负权边）解决单源点最短路径问题。不允许边的权是负权，如果遇到负权，则可以采用Bellman-Ford算法.算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队，直到队列为空时算法结束。
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.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
c.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
5.3算法适用范围
⑴单源最短路径； 
⑵有向图和无向图；
⑶ 边权可正可负；
⑷差分约束系统。
5.4算法实例

图3 无向图
根据图3，用Bellman-Ford算法找出以a为起点的单源最短路径步骤如下表3：
表3 Bellman-Ford算法步骤流程
k
distk[a]
distk[b]
distk[c]
distk[d]
distk[e]
distk[f]
1
0
2
5
1
*
*
2
0
2
4
1
2
10
3
0
2
3
1
2
4
4
0
2
3
1
2
4

5
0
2
3
1
2
4
6.几种算法的比较
Floyd算法适用于是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。其优点是容易理解，可以算出任意两个节点之间的最短距离，代码编写简单 。但是时间复杂度比较高，不适合计算大量数据。
Dijkstra(迪杰斯特拉)算法是一种按路径长度递增的次序产生最短路径的算法，可求单源、无负权的最短路。其适用于有向图及无向图，时效性较好，时间复杂度为O（V*V+E）,可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。但是由于其遍历计算的节点很多，所以算法的效率较低。
Bellman-Ford算法是求解单源最短路问题的一种算法，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去，而Bellman-Ford算法具有分辨这种负环路的能力。
7. 总结
Floyd算法、Dijkstra算法和Bellman-Ford算法是目前的最短路径算法中较为常用的三个算法。每种算法都有其自己的特点和优势。比方说若路径规划问题较为简单，可采用Floyd算法；若路径规划问题涉及到负权边，可采用Bellman-Ford算法。总之，在实际应用中，根据路径问题的特点采用合理的路径规划算法，方能达到最优的效果。

参考文献
[1] 杨丽萍.最短路径算法在校园导游系统中的应用.计算机时代,2014(2)
[2] 吴家琴.基于迪杰斯特洛模型的物流运输最短路径的选择.物流技术,2013(11)
[3] 王春霞,黄甜.最短路径算法在校园地理信息系统中的应用.长春师范学院学报.2013(6)
[4] 刘文海,徐荣聪.几种最短路径的算法及比较.福建电脑,2008(2)