使用BellmanFord算法求带负权图的单源最短路径

使用BellmanFord算法求带负权图的单源最短路径

BellmanFord算法可以处理带不带负权环的图,及时权为负也可以接受,但是时间复杂度较高

贝尔曼-福特算法与迪科斯彻算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。在两个算法中,计算时每个边之间的估计距离值都比真实值大,并且被新找到路径的最小长度替代。 然而,迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点,然后对其的出边进行松弛操作;而贝尔曼-福特算法简单地对所有边进行松弛操作,共 |V|-1次,其中 |V|}是图的点的数量。在重复地计算中,已计算得到正确的距离的边的数量不断增加,直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

贝尔曼-福特算法的最多运行 $O(|V|*|E|)$(大O符号)次, |V|,|E|别是节点和边的数量)。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
package ShortestPath;

import java.util.Stack;
import java.util.Vector;

/**
* @ Description: 使用BellmanFord算法求最短路径
* @ Date: Created in 14:20 2018/8/2
* @ Author: Anthony_Duan
*/
public class BellmanFord<Weight extends Number & Comparable>{

//图的引用
private WeightedGraph G;

//起始点
private int s;

//distTo[i]存储从起始点s到i的最短路径长度
private Number[] distTo;
// from[i]记录最短路径中到达[i]点的边是哪一条 可以用来恢复整个最短路径
Edge<Weight>[] from;
//标记图中是否有负权环
boolean hasNegativeCycle;

//构造函数 使用BellmanFord算法求最短路径
public BellmanFord(WeightedGraph graph, int s) {

G = graph;
this.s = s;
distTo = new Number[G.V()];
from = new Edge[G.V()];
//初始化所有的节点s都不可达,由from数组表示

for (int i = 0; i < G.V(); i++) {
from[i] = null;
}
// 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
distTo[s] = 0.0;
from[s] = new Edge<Weight>(s, s, (Weight) (Number) (0.0));


// Bellman-Ford的过程
// 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离
for (int pass = 0; pass < G.V(); pass++) {
// 每次循环中对所有的边进行一遍松弛操作
// 遍历所有边的方式是先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边
for (int i = 0; i < G.V(); i++) {
for (Object item : G.adj(i)) {
Edge<Weight> e = (Edge<Weight>) item;

// 对于每一个边首先判断e->v()可达
// 之后看如果e->w()以前没有到达过, 显然我们可以更新distTo[e->w()]
// 或者e->w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离, 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()]
if (from[e.v()] != null && (from[e.w()] == null
|| distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue())) {
distTo[e.w()] = distTo[e.v()].doubleValue() + e.wt().doubleValue();
from[e.w()] = e;
}
}
}
}

hasNegativeCycle = detectNegativeCycle();

}
// 判断图中是否有负权环
boolean detectNegativeCycle() {
for (int i = 0; i < G.V(); i++) {
for (Object item :
G.adj(i)) {
Edge<Weight> e = (Edge<Weight>) item;
if (from[e.v()] != null && distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue()) {
return true;
}
}
}
return false;
}

//返回图中是否有负权环
boolean negativeCycle() {
return hasNegativeCycle;
}


// 返回从s点到w点的最短路径长度
Number shortestPathTo(int w) {
assert w >= 0 && w < G.V();
assert !hasNegativeCycle;
assert hasPathTo(w);
return distTo[w];
}

// 判断从s点到w点是否联通
boolean hasPathTo(int w) {
assert (w >= 0 && w < G.V());
return from[w] != null;
}
// 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
Vector<Edge<Weight>> shortestPath(int w){

assert w >= 0 && w < G.V() ;
assert !hasNegativeCycle ;
assert hasPathTo(w) ;

// 通过from数组逆向查找到从s到w的路径, 存放到栈中

Stack<Edge<Weight>> s = new Stack<Edge<Weight>>();
Edge<Weight> e = from[w];
while( e.v() != this.s ){
s.push(e);
e = from[e.v()];
}
s.push(e);

// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Edge<Weight>> res = new Vector<Edge<Weight>>();
while( !s.empty() ){
e = s.pop();
res.add(e);
}

return res;
}

// 打印出从s点到w点的路径
void showPath(int w){

assert( w >= 0 && w < G.V() );
assert( !hasNegativeCycle );
assert( hasPathTo(w) );

Vector<Edge<Weight>> res = shortestPath(w);
for( int i = 0 ; i < res.size() ; i ++ ){
System.out.print(res.elementAt(i).v() + " -> ");
if( i == res.size()-1 ) {
System.out.println(res.elementAt(i).w());
}
}
}

// 测试我们的Bellman-Ford最短路径算法
public static void main(String[] args) {

String filename = "/Users/duanjiaxing/IdeaProjects/Algorithm/src/ShortestPath/testG2.txt";
//String filename = "testG_negative_circle.txt";
int V = 5;

SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

System.out.println("Test Bellman-Ford:\n");

int s = 0;
BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g, s);
if( bellmanFord.negativeCycle() ) {
System.out.println("The graph contain negative cycle!");
} else {
for( int i = 0 ; i < V ; i ++ ){
if(i == s) {
continue;
}

if(bellmanFord.hasPathTo(i)) {
System.out.println("Shortest Path to " + i + " : " + bellmanFord.shortestPathTo(i));
bellmanFord.showPath(i);
}
else {
System.out.println("No Path to " + i );
}

System.out.println("----------");
}
}

}
}
-------------End Of This ArticleThank You For Reading-------------