贝尔曼福特算法
松弛算法
想像一下图论中的graph 是用毛线和珠子组成的网状结构，两颗珠子之间毛线的长度即edge上的权值，一开始十分松乱的放在桌上。现在你要求SSSP(单源最短路)，当发现从源点s到当前点u有两条路径，relax操作可以想象成用力把s和u两点往外撑开。这时候依照生活经验，我们可以很自然的看到s点和u点之间较短的那条边处于紧绷状态，而较长的那条边处于松弛状态。因此非常形象的把这个操作称为松弛操作。
负环路
负环路（环路权重之和为负数）
Bellman Ford算法每次对所有的边进行松弛，每次松弛都会得到一条最短路径，所以总共需要要做的松弛操作是V - 1次。在完成这么多次松弛后如果还是可以松弛的话，那么就意味着，其中包含负环。
思路
初始化时将起点s到各个顶点v的距离dist(s->v)赋值为∞，dist(s->s)赋值为0
后续进行最多n-1次遍历操作(n为顶点个数,上标的v输入法打不出来…),对所有的边进行松弛操作,假设:
所谓的松弛，以边ab为例，若dist(a)代表起点s到达a点所需要花费的总数， dist(b)代表起点s到达b点所需要花费的总数,weight(ab)代表边ab的权重， 若存在:
(dist(a) +weight(ab)) < dist(b)
则说明存在到b的更短的路径,s->…->a->b,更新b点的总花费为(dist(a) +weight(ab))，父节点为a
遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路
思路上与狄克斯特拉算法(Dijkstra algorithm)最大的不同是每次都是从源点s重新出发进行”松弛”更新操作，而Dijkstra则是从源点出发向外扩逐个处理相邻的节点，不会去重复处理节点，这边也可以看出Dijkstra效率相对更高点。
Java实现
如下图，求出A到各节点的最短路径
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
| public class BellmanFord {
public static void main(String[] args){
Edge ab = new Edge("A", "B", -1);
Edge ac = new Edge("A", "C", 4);
Edge bc = new Edge("B", "C", 3);
Edge be = new Edge("B", "E", 2);
Edge ed = new Edge("E", "D", -3);
Edge dc = new Edge("D", "C", 5);
Edge bd = new Edge("B", "D", 2);
Edge db = new Edge("D", "B", 1);
Edge[] edges = new Edge[] {ab,ac,bc,be,bd,ed,dc,db};
HashMap<String,Integer> costMap = new HashMap<String,Integer>();
HashMap<String,String> parentMap = new HashMap<String,String>();
costMap.put("A", 0);
costMap.put("B", Integer.MAX_VALUE);
costMap.put("C", Integer.MAX_VALUE);
costMap.put("D", Integer.MAX_VALUE);
costMap.put("E", Integer.MAX_VALUE);
for(int i =1; i< costMap.size();i++) {
boolean hasChange = false;
for(int j =0; j< edges.length;j++) {
Edge edge = edges[j];
int startPointCost = costMap.get(edge.getStartPoint()) == null ? 0:costMap.get(edge.getStartPoint());
int endPointCost = costMap.get(edge.getEndPoint()) == null ? Integer.MAX_VALUE : costMap.get(edge.getEndPoint());
if(endPointCost > (startPointCost + edge.getWeight())) {
costMap.put(edge.getEndPoint(), startPointCost + edge.getWeight());
parentMap.put(edge.getEndPoint(), edge.getStartPoint());
hasChange = true;
}
}
if (!hasChange) {
break;
}
}
boolean hasRing = false;
for(int j =0; j< edges.length;j++) {
Edge edge = edges[j];
int startPointCost = costMap.get(edge.getStartPoint()) == null ? 0:costMap.get(edge.getStartPoint());
int endPointCost = costMap.get(edge.getEndPoint()) == null ? Integer.MAX_VALUE : costMap.get(edge.getEndPoint());
if(endPointCost > (startPointCost + edge.getWeight())) {
System.out.print("\n图中存在负环路，无法求解\n");
hasRing = true;
break;
}
}
if(!hasRing) {
for(String key : costMap.keySet()) {
System.out.print("\n到目标节点"+key+"最低耗费:"+costMap.get(key));
if(parentMap.containsKey(key)) {
List<String> pathList = new ArrayList<String>();
String parentKey = parentMap.get(key);
while (parentKey!=null) {
pathList.add(0, parentKey);
parentKey = parentMap.get(parentKey);
}
pathList.add(key);
String path="";
for(String k:pathList) {
path = path.equals("") ? path : path + " --> ";
path = path + k ;
}
System.out.print("，路线为"+path);
}
}
}
}
static class Edge{
private String startPoint;
private String endPoint;
private int weight;
public Edge(String startPoint,String endPoint,int weight) {
this.startPoint = startPoint;
this.endPoint = endPoint;
this.weight = weight;
}
public String getStartPoint() {
return startPoint;
}
public String getEndPoint() {
return endPoint;
}
public int getWeight() {
return weight;
}
}
}
|
问题
为什么循环n-1次
首先明确，不是这个算法规定了一定要n-1次循环
而是这个算法最坏的情况下需要n-1次循环。
什么情况下最好?
这是我们的图： 很简单的一个图，四个节点，三个边（长度分别是：3 7 12）
1
| 1 --(3)---2--(7)---3--(12)--4
|
让你求出，从1出发的最短路径
1 .假如题目这样描述：
能理解吧？ （起点，终点， 长度）
关键就在于我们从上到下按顺序，把这三个边， 依次存进了 你的 edge[] 数组里面。
来看看Bellman算法的代码中，我们是咋操作的
- 先把dis 数组，起点处设置为 0 ， 其它点设置为INF， dis[1] = 0 , 其他的dis[] =INF
- 对于每一次循环， 算法要求我们，更新 m 条边。
1
2
3
4
5
6
7
8
| for(i=0;i<n;i++){
for(j=0;j<m;j++){
int u=e[j].u,v=e[j].v;
if(d[u]!=INF&&d[u]+w[u][v]<d[v]) {
d[v]=d[u]+w[u][v];
}
}
}
|
我们来动手做一下
1
2
3
4
5
6
7
8
9
10
11
12
| 第一次循环。。。。。。
dis[1]=0
dis[2] =3 ，因为 dis[1] + map[1][2] < dis[2]，也就是 3 + 0 <INF
dis[3] = 10 ,同理
dis[4] = 22 , 同理
第二次循环。。。。。。。
dis[1] =0
dis[2] = 3
dis[3] =10
dis[4] = 22 ,啥都没做
第三次循环。。。。。。
也啥都没做
|
发现了吗？ 我们仅仅一次循环就出结果了，谁还费那劲要做n-1 次循环？？？？
但是，如果是这种呢？
2 .假如题目这样描述：
我们再动手操作一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 第一次循环。。。。。。
dis[4]=inf
dis[3]=inf ，
dis[2] =3 ,
dis[1]= 0 ,
第二次循环。。。。。。。
dis[4]=inf
dis[3]= 10 ，
dis[2] =3 ,
dis[1]= 0 ,
第三次循环。。。。。。
dis[4]=22
dis[3]=10，
dis[2] =3 ,
dis[1]= 0 ,
|
我们必须，做n-1次循环，才能出结果
原因就是：
1
2
3
| 我们按顺序存入边，
但是这个顺序有时候很好，（我们第一次循环就是从前往后循环），导致第一次循环就更新了 所有的节点
这个顺序有时候很差（我们每次都是从路径的后面向前面更新），导致每次循环仅仅更新一个
|
所以，我们为了应对最差情况，不得不更新n-1次。
现在你懂了为啥循环中间有个剪枝了吧，就是担心情况太好， 导致后面的循环白白浪费时间，早点剪枝跳出循环。
