路由选择算法改进

1、Bellman-Ford算法及其优化一、引言Bellman-Ford算法与另一个非常著名的Dijkstra算法一样，用于求解单源 点最短路径问题。Bellman-ford算法除了可求解边权均非负的问题外，还可以解 决存在负权边的问题（意义是什么，好好思考），而Dijkstra算法只能处理边权 非负的问题，因此 Bellman-Ford算法的适用面要广泛一些。但是，原始的 Bellman-Ford算法时间复杂度为O（VE），比Dijkstra算法的时间复杂度高，所 以常常被众多的大学算法教科书所忽略，就连经典的算法导论也只介绍了基 本的Bellman-Ford算法，在国内常见的基本信息学奥赛教材

2、中也均未提及，因 此该算法的知名度与被掌握度都不如 Dijkstra算法。事实上，有多种形式的 Bellman-Ford算法的优化实现。这些优化实现在时间效率上得到相当提升，例如 近一两年被热捧的SPFA（ Shortest-Path Faster Algoithm 更快的最短路径算法） 算法的时间效率甚至由于Dijkstra算法，因此成为信息学奥赛选于经常讨论的话 题。然而，限于资料匮乏，有关Bellman-Ford算法的诸多问题常常困扰奥赛选 手。如：该算法值得掌握么？怎样用编程语言具体实现？有哪些优化？与SPFA 算法有关系么？本文试图对Bellman-Ford算法做一个比较全面的介绍。

3、二、国内外的研究现状1、Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短 路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。2、Floyd算法适用于APSP（All Pairs Shortest Paths），是一种动态规划算法，稠密 图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠 密图，效率要高于执行IVI次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单 缺点：时间复杂度比较高，不适合计算大量数据。三、B

4、ellman-Ford算法思想Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径 问题。对于给定的带权(有向或无向)图G= (V,E),其源点为s,加权函数w 是 边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明 图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给 出从源点s到图G的任意顶点v的最短路径dv。Bellman-Ford算法流程分为三个阶段：初始化：将除源点外的所有顶点的最短距离估计值dv -+s, ds 。； 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V 中的每个顶点v的最短距离估计值逐步逼

5、近其最短距离；(运行IvI-1次)检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如 果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并 且从源点可达的顶点v的最短距离保存在dv中。算法描述如下：Bellman-Ford(G,w,s) : boolean 图 G，边集函数 w，s 为源点for each vertex v E V (G) do 初始化 1 阶段dv +sds -0; /1阶段结束for i=1 to lvl-1 do /2阶段开始，双重循环。for each edge (u,v) EE(G) do 边集数组要用到，穷举每条边。If dv d

6、u+ w(u,v) then 松弛判断dv=du+w(u,v) 松弛操作2阶段结束for each edge (u,v) EE(G) doIf dv du+ w(u,v) thenExit falseExit true下面给出描述性证明：首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回 路，因此它最多包含lvl-1条边。其次，从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成 一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按 顶点距离s的层次，逐层生成这棵最短路径树的过程。在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那

7、些树 枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边 进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连 的那些顶点的最短路径.。因为最短路径最多只包含lvl-1条边，所以，只需 要循环lvl-1次。每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后 这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。(但是， 每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？) 如果没有负权回路，由于最短路径树的高度最多只能是lvl-1，所以最多经过 lvl-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果d

8、v仍保持 +皿则表明从s到v不可达。如果有负权回路，那么第lvl-1遍松弛操作仍然会成功，这时，负权回路上 的顶点不会收敛。例如对于上图，边上方框中的数字代表权值，顶点A,B,C之间存在负权回路。 S是源点，顶点中数字表示运行Bellman-Ford算法后各点的最短距离估计值。此时da的值为1，大于dc+w(c,a)的值-2，由此da可以松弛为-2，然后 db又可以松弛为-5,dc又可以松弛为-7.下一个周期，da又可以更新为更小的 值，这个过程永远不会终止。因此，在迭代求解最短路径阶段结束后，可以通过 检验边集E的每条边(u,v)是否满足关系式dv du+ w(u,v)来判断是否存在负 权回

9、路。Bellman-Ford算法能在一般情况下(存在负权边的情况)下，解决单源最短 路径问题。对于给定的带权有向图G = (V, E)，其源点为s，加权函数为w： E 一 R，对该图运行Bellman-Ford算法后可以返回一个布尔值，表明图中是否存在 着一个从源点可达的权为负的回路。若存在这样的回路，问题无解；否则，算法 产生最短路径及其权值。Bellman-Ford算法运用松弛技术，对每个顶点v，逐步减小从源s到v的 最短路径的权的估计值dv直至其可达到实际最短路径的权S(s, v)。算法返 回布尔值True，当且仅当图中不包含从源点可达的负权回路。伪代码：BELLMAN-FORD(G w

10、, s)INITIALIZE-SINGLE-SOURCE(G, s)for i，1 to |VG| -do for each edge (u, v) e EGdo RELAX(u, v, w)for each edge (u, v) e EGdo if dv du + w(u, v)then return FALSEreturn TRUE第1行初始化每个顶点的d和n值后，算法对图中的边进行了 |V| - 1 遍操作。每一遍都是第24行for循环的一次迭代，有点类似于预处理。下边 是的图示是算法对边进行四遍操作，每一遍过后的状态。在|V- 1|遍操作过后， 第58行对负权回路进行检查，并返回适当

11、的布尔值。图示：源点是顶点s。d值被标记在顶点内，阴影覆盖的边指示了前趋值：如果 边（u, v）被阴影覆盖，则nv = u。在这个特定例子中，每一趟按照如下的顺 序对边进行松弛：（t，x），（t，y），（t，z），（x，t），（y，x），（y，z），（z，x），（z， s），（s，t），（s，y）。a）示出了对边进行第一趟操作前的情况。b）e）示出了每一 趟连续对边操作后的情况。e）中d和n值是最终结果。这个例子中，返回值 是 True。理解最短路算法，最基础，最简单，最经典的要数这个题目：HDU 2544最 短路，用Bellon-Ford算法实现：（必然有最短路，所以不必判断布尔值）0 #i

12、nclude#include0 #include#include0 #includeusing namespacestd;0const int NV =101;struct Edge 0int u, v, w;graNV * NV;0 int disNV;void BellmanFord(int n, int m) 0 memset(dis, 0 x7f, sizeof(dis);dis1 = 0;0 for (int i = 1; i n; i+) for (int j = 0; j m; j+) 0 if (disgraj.u + graj.w disgraj.v) 1 disgraj.v

13、 = disgraj.u + graj.w; 01 if (disgraj.v + graj.w 1 disgraj.u) 1 disgraj.u = disgraj.v + graj.w;2131int main() 1 int n, m;while (scanf(%d %d, &n, &m), n I m)1for (int i = 0; i m; i+) 1 int u, v, w;scanf(%d %d %d”, &u, &v, &w);1 grai.u = u, grai.v = v, grai.w =8901234567890123456789w;BellmanFord(n, m)

14、;printf(%dn, disn);2 return 0;22222222333333333314243Bellman-Ford虽然很简单，但是复杂度太高，达到了 O(VE)，从上边图示中 可以看出：(a) t，x，y，z边的松弛是无用操作；(b) s，x，z边的松弛是无用操 作；(c) s，t，y边的松弛是无用操作；(d) s，x，y，z边的松弛是无用操作。也 就是说，只有更新过的点所做的松弛才是有效操作，所以出现了更高效的算法， 即 SPFA：四、Bellman-Ford 算法的优化SPFA(Shortest PathFaster Algorithm)算法SPFA算法是西南交通大学段凡丁

15、于1994年发表的。它是Bellman-Ford的 队列优化，时效性相对好，时间复杂度O(kE)，也是单源最短路算法，同时可 以处理负权边。从名字即可看出，此算法速度非同一般。与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一 个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维 护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他 的节点，从而大大减少了重复的操作次数。伪代码：SPFA(Gw,s)INITIALIZE-SINGLE-SOURCE(GjS)INITIALIZE-QUEUE(Q)ENQUEUE(Q,s)While

16、 Not EMPTY(Q)Do u-DLQUEUE(Q)For 每条边(u,v) in EGDo tmp-dvRelax(u,v,w)If (dv tmp) and (v 不在 Q 中)ENQUEUE(Q,v)Bellon-Ford算法，每次都松弛所有的边，所以造成效率低下，而SPFA的高 效之处在于，它每次只松弛更新过的点连接的边，简单的过程叙述就是：初始Diss = 0，其他赋值为Inf；将起点s放入空队列Q；step 1.从Q中选取元素u，并删除该元素；step 2.对所有和u相连的点v进行松弛，如果v被更新且v不在队 列中，把v加进队列；5) 一直循环step 1和step 2,直到队

17、列为空。结束;另外，还需要了解的是，SPFA的算法时间效率是不稳定的，即它对于不同 的图所需要的时间有很大的差别。在最好情形下，每一个节点都只入队一次，则 算法实际上变为广度优先遍历，其时间复杂度仅为0(E)。另一方面，存在这样 的例子，使得每一个节点都被入队(V -1)次，此时算法退化为Bellman-ford算法， 其时间复杂度为O(VE)。SPFA在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表 现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳 定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA算法在一类网格 图中的表现不尽如

18、人意。还是上边那道题，用SPFA算法实现：1)邻接矩阵实现，便于理解算法过程：01#include02#include03#include04#include05#include06#include07using namespace std;08const int NV = 101;09const int inf = INT_MAX 1;10int m, n;11int mapNVNV;12int disNV;13bool markNV;14int Spfa (int src, int des) (15for (int i = 0; i = n; i+) (16marki = false;17

19、disi = inf;18)19queue Q;20marksrc = true;21dissrc = 0;22Q.push(src);23while (!Q.empty() (24int first = Q.front();25Q.pop();26markfirst = false;27for (int i = 1; i = n; i+) (28if (disfirst + mapfirsti disi) (29if (!marki) (30Q.push(i);31)32disi = disfirst + mapfirsti;33marki = true;34)/for/while37ret

20、urn disdes;38)39int main() (40while (scanf(%d%d, &n, &m), n | m) ( 41int a, b, c;42for (int i = 1; i = n; i+) (43mapii = inf;44for (int j = i + 1; j = n; j+) (45mapij = mapji = inf;46)47)48while (m-) (49scanf(%d%d%d, &a, &b, &c);50mapab = mapba = c;51)52printf(%dn, Spfa(1, n);53)54return 0;55)2)更通用的

21、邻接表形式：01#include02#include03#include04#include05#include06#include07#include08#include09using namespace std;10const int NV = 101;11const int NE = 20001;12const int inf = INT_MAX 1;13struct SPFA (14int n, size;15int disNV, headNV;16bool inNV;17struct edge (18int v, w, next;19edge () ()20edge (int V,

22、int NEXT, int W = 0) : v(V), next(NEXT), w(W) () 21ENE;22void init(int nn) (23n = nn, size = 0;24for (int i = 0; i = n; i+) (25headi = -1;26ini = 0;27disi = inf;282930inline void insert(int u, int v, int w) (31Esize = edge(v, headu, w);32headu = size+;3334inline bool relax(int u, int v, int w) (35if

23、 (disv = inf| disu + w disv) (36disv = disu +w;37return true;3839return false;4041int spfa(int src,int des) (42queue que;43dissrc = 0;44que.push(src);45insrc = true;46while (!que.empty() (47int u = que.front();48que.pop();49inu = false;50for (int i = headu; i != -1; i = Ei.next) (51int v = Ei.v;52if

24、 (relax(u, v, Ei.w) & !inv ) (53inv = true;54que.push(v);55/if56/for57/while58return disdes;59)/SFPA60G;61int main() (62int n, m;63while (scanf(%d%d, &n, &m), n | m) ( 64G.init(n);65int a, b, c;66for (int i = 0; i m; i+) (67scanf(%d%d%d, &a, &b, &c);68G.insert(a, b, c);69G.insert(b, a, c);70)71printf(%dn, G.spfa(1, n);72)73return 0;74)7576777五、理论分析与算法比较图论中求最短路一般有四种比较常见的算法：Floyd、Dijkstra、Bell