Mixing
贝尔曼-福特算法
body.skin-minerva .mw-parser-output table.infobox caption{text-align:center}
| 分类 | 单源最短路径问题（针对带权有向图） |
|---|---|
| 数据结构 | 图 |
| 最坏时间复杂度 | O(|V||E|){displaystyle Oleft(|V||E|right)}  |
| 最坏空间复杂度 | O(|V|){displaystyle O(|V|)}  |
图与树 搜索算法 |
|---|
|
分类 |
|
相关主题 |
|
贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·貝尔曼（Richard Bellman） 和 萊斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行|V|−1{displaystyle |V|-1}
目录
1 算法
1.1 pseudocode
2 原理
2.1 松弛
2.2 负边权操作
2.3 负权环判定
3 优化
3.1 循环的提前跳出
3.2 队列优化
4 样例
5 参考文献
算法
在这个图中，假设A是起点，并且边以最坏的顺序处理，从右到左，需要|V|−1{displaystyle |V|-1}
步或4{displaystyle 4}
次计算路径长度。相反地，若边以最优顺序处理，从左到右，算法只需要在一次遍历内完成。贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。
然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共|V|−1{displaystyle |V|-1}
贝尔曼-福特算法的最多运行O(|V|⋅|E|){displaystyle O(|V|cdot |E|)}
pseudocode
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{displaystyle n}
负边权操作
与迪科斯彻算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。
负权环判定
因为负权环可以无限制的降低总花费，所以如果发现第n{displaystyle n}
优化
循环的提前跳出
在实际操作中，贝尔曼-福特算法经常会在未达到|V|−1{displaystyle |V|-1}
队列优化
西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为O(k|E|){displaystyle O(k|E|)}
Pascal语言示例
1 Begin
2 initialize-single-source(G,s);
3 initialize-queue(Q);
4 enqueue(Q,s);
5 while not empty(Q) do
6 begin
7 u:=dequeue(Q);
8 for each v∈adj[u] do
9 begin
10 tmp:=d[v];
11 relax(u,v);
12 if (tmp<>d[v]) and (not v in Q) then
13 enqueue(Q,v);
14 end;
15 end;
16 End;
C++语言示例
1 int SPFA(int s) {
2 queue<int> q;
3 bool inq[maxn] = {false};
4 for(int i = 1; i <= N; i++) dis[i] = 2147483647;
5 dis[s] = 0;
6 q.push(s); inq[s] = true;
7 while(!q.empty()) {
8 int x = q.front(); q.pop();
9 inq[x] = false;
10 for(int i = front[x]; i !=0 ; i = e[i].next) {
11 int k = e[i].v;
12 if(dis[k] > dis[x] + e[i].w) {
13 dis[k] = dis[x] + e[i].w;
14 if(!inq[k]) {
15 inq[k] = true;
16 q.push(k);
17 }
18 }
19 }
20 }
21 for(int i = 1; i <= N; i++) cout << dis[i] << ' ';
22 cout << endl;
23 return 0;
24 }
样例
例：
- V={v1,v2,v3,v4},E={(v1,v2),(v1,v3),(v2,v4),(v4,v3)},weight(v1,v2)=−1,weight(v1,v3)=3,weight(v2,v4)=3,weight(v4,v3)=−1{displaystyle V={v_{1},v_{2},v_{3},v_{4}},E={(v_{1},v_{2}),(v_{1},v_{3}),(v_{2},v_{4}),(v_{4},v_{3})},weight(v_{1},v_{2})=-1,weight(v_{1},v_{3})=3,weight(v_{2},v_{4})=3,weight(v_{4},v_{3})=-1}
运行如表： D:Dist[v],P:Pred[v]{displaystyle D:{texttt {Dist}}[v],P:{texttt {Pred}}[v]}
![{displaystyle D:{texttt {Dist}}[v],P:{texttt {Pred}}[v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c143508d1fc5c969e32c0dd5aaf6c47c571cf13a)
| 点 | v1{displaystyle v_{1}}  | v2{displaystyle v_{2}}  | v3{displaystyle v_{3}}  | v4{displaystyle v_{4}}  |
|---|---|---|---|---|
D/P{displaystyle D/P}  | D/P{displaystyle D/P} | D/P{displaystyle D/P} | D/P{displaystyle D/P} | |
| 初始化 | 0/null{displaystyle 0/{texttt {null}}}  | ∞/null{displaystyle infty /{texttt {null}}}  | ∞/null{displaystyle infty /{texttt {null}}} | ∞/null{displaystyle infty /{texttt {null}}} |
| 循环第一次 | 0/null{displaystyle 0/{texttt {null}}} | −1/v1{displaystyle -1/v_{1}}  | 3/v1{displaystyle 3/v_{1}}  | ∞/null{displaystyle infty /{texttt {null}}} |
| 循环第二次 | 0/null{displaystyle 0/{texttt {null}}} | −1/v1{displaystyle -1/v_{1}} | 3/v1{displaystyle 3/v_{1}} | 2/v2{displaystyle 2/v_{2}}  |
| 循环第三次 | 0/null{displaystyle 0/{texttt {null}}} | −1/v1{displaystyle -1/v_{1}} | 1/v4{displaystyle 1/v_{4}}  | 2/v2{displaystyle 2/v_{2}} |
参考文献
^ http://www.cnki.com.cn/Article/CJFDTotal-XNJT402.015.htm
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Comments
Post a Comment