贝尔曼-福特算法 - 维基百科,自由的百科全书
贝尔曼-福特算法 | |
---|---|
概况 | |
類別 | 最短路径问题(针对带权有向图) |
資料結構 | 图 |
复杂度 | |
最坏时间复杂度 | |
最优时间复杂度 | |
空間複雜度 | |
相关变量的定义 |
图与树 搜索算法 |
---|
分类 |
相关主题 |
贝尔曼-福特算法(英語:Bellman–Ford algorithm),求解单源最短路径问题的一种算法,由理查德·貝尔曼和小萊斯特·倫道夫·福特创立。有时候这种算法也被称为貝爾曼-福特-摩爾算法(Bellman–Ford–Moore algorithm),因为愛德華·F·摩爾也为这个算法的发展做出了贡献。它的原理是对图进行次松弛操作,得到所有可能的最短路径。其优于戴克斯特拉算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达。但算法可以进行若干种优化,提高了效率。
算法
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/85/Bellman-Ford_worst-case_example.svg/220px-Bellman-Ford_worst-case_example.svg.png)
贝尔曼-福特算法与戴克斯特拉演算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。在两个算法中,计算时每个边之间的估计距离值都比真实值大,并且被新找到路径的最小长度替代。 然而,戴克斯特拉演算法以贪心法选取未被处理的具有最小权值的节点,然后对其的出边进行松弛操作;而贝尔曼-福特算法简单地对所有边进行松弛操作,共次,其中是图的点的数量。在重复地计算中,已计算得到正确的距离的边的数量不断增加,直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比戴克斯特拉演算法适用于更多种类的输入。
贝尔曼-福特算法的最多运行(大O符号)次,和分别是节点和边的数量)。
偽代碼
[编辑]procedure BellmanFord(list vertices, list edges, vertex source) // 读入边和节点的列表 // 初始化图 distance为∞,predecessor为空 for each vertex v in vertices: if v is source then distance[v] := 0 else distance[v] := infinity predecessor[v] := null // 对所有节点 for i from 1 to size(vertices)-1: //检查每条边 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // 检查是否有负权重的回路 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "图包含负权重的回路"
原理
[编辑]循环
[编辑]每次循环操作实际上是对相邻节点的访问,第次循环操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过条边,所以可知贝尔曼-福特算法所得为最短路径。
负边权操作
[编辑]与戴克斯特拉演算法不同的是,戴克斯特拉演算法的基本操作“拓展”是在深度上寻路,而“松弛”操作则是在广度上寻路,这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。
负权环判定
[编辑]因为负权环可以无限制的降低总花费,所以如果发现第次操作仍可降低花销,就一定存在负权环。
尋找負迴路
[编辑]當使用這個算法尋找最短路徑時,有負迴路會使算法找不到正確的答案。但是,由於在找到負迴路後會中止算法,所以可以被用來尋找目標,例如在網路流分析中的消圈演算法(Cycle Cancellation Algorithms)
优化
[编辑]循环的提前跳出
[编辑]在实际操作中,贝尔曼-福特算法经常会在未达到次前就出解,其实是最大值。于是可以在循环中设置判定,在某次循环不再进行松弛时,直接退出循环,进行负权环判定。
队列优化
[编辑]西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上,用一个队列记录松弛过的节点,可以避免了冗余计算。原文中提出该算法的复杂度为,是个比较小的系数,[1]但该结论被证明不适于于所有情况。[來源請求]
Pascal语言示例
Begin initialize-single-source(G,s); initialize-queue(Q); enqueue(Q,s); while not empty(Q) do begin u:=dequeue(Q); for each v∈adj[u] do begin tmp:=d[v]; relax(u,v); if (tmp<>d[v]) and (not v in Q) then enqueue(Q,v); end; end; End;
C++语言示例
int SPFA(int s) { std::queue<int> q; bool inq[maxn] = {false}; for(int i = 1; i <= N; i++) dis[i] = 2147483647; dis[s] = 0; q.push(s); inq[s] = true; while(!q.empty()) { int x = q.front(); q.pop(); inq[x] = false; for(int i = front[x]; i !=0 ; i = e[i].next) { int k = e[i].v; if(dis[k] > dis[x] + e[i].w) { dis[k] = dis[x] + e[i].w; if(!inq[k]) { inq[k] = true; q.push(k); } } } } for(int i = 1; i <= N; i++) std::cout << dis[i] << ' '; std::cout << std::endl; return 0; }
样例
[编辑]例:
- ,。
运行如表:
点 | ||||
---|---|---|---|---|
初始化 | ||||
循环第一次 | ||||
循环第二次 | ||||
循环第三次 |
参考文献
[编辑]
|