算法十二:Bellman-Ford算法 - 一个点到其他所有点的最短路径(可负边)
什么是Bellman-Ford算法?Bellman-Ford算法是一种堪称完美的解决一个点到其他各点的最短路径的算法。Bellman-Ford算法的核心代码只有4行,可以解决负权边的问题。
Bellman-Ford算法的核心代码只有四行,如下
for(k=1; k<=n-1; k++)
for(i=1; i<=m; i++)
if(dis[v[i]] > dis[u[i]] + w[i])
dis[v[i]] = dis[u[i]] + w[i];
Bellman-Ford算法的核心代码意思是:遍历每一个点,其中每一次遍历时,遍历所有的边,对每个边进行一次松弛操作。
松弛什么?请点击查看。算法十一:Dijkstra算法 - 一个点到各个点的最短路径
现在有如下图,共5个点5条边,边都是有向边,其中点1到点2的距离为负数。如下:
为什么会进行n-1次的循环呢?因为在不包含负权回路的路径中,n个点最多有n-1条边。在负权边中,负权回路会使最短路径不断的变小,永无止境。
完整代码如下:
#include <stdio.h>
int main(){
int dis[10], i, k, m, n, u[10], v[10], w[10];
int maxValue = 9999;
//源点为1
int start = 1;
//读入点的个数n,边的个数m
scanf("%d %d", &n, &m);
//读入边
for(i=1; i<=m; i++){
scanf("%d %d %d", &u[i], &v[i], &w[i]);
}
//初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大
for(i=0; i<=n; i++){
dis[i] = maxValue;
}
//源点到源点的距离为0
dis[start] = 0;
//Bellman-Ford算法的核心语句
for(k=1; k<=n-1; k++){
for(i=1; i<=m; i++){
if(dis[v[i]] > dis[u[i]] + w[i]){
dis[v[i]] = dis[u[i]] + w[i];
}
}
}
for(i=1; i<=n; i++){
printf("%d ", dis[i]);
}
return 0;
}
输入:
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
//输出:
0 -3 -1 2 4
Bellman-Ford算法的时间复杂对为O(MN)。
我们可以更加完善上面的代码。比如我们已经知道了使用Bellman-Ford算法不能包含负权回路,那么我们需要检测图中是否包含负权回路:
sign = 0
for(i=1; i<=m; i++)
if(dis[v[i]] > dis[u[i]] + w[i])
flag = 1;
if(sign == 1)
printf("此图有负权回路");
另外,在n-1轮循环中,若n-3轮已经松弛完毕,那么n-2和n-1两次循环便毫无意义,因此增加判断,若第x轮dis数组已经不再发生变化了,则不在继续进行循环。
新版的完整代码如下:
#include <stdio.h>
int main(){
int dis[10], i, k, m, n, u[10], v[10], w[10], sign, check;
int maxValue = 9999;
//源点为1
int start = 1;
//读入点的个数n,边的个数m
scanf("%d %d", &n, &m);
//读入边
for(i=1; i<=m; i++){
scanf("%d %d %d", &u[i], &v[i], &w[i]);
}
//初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大
for(i=0; i<=n; i++){
dis[i] = maxValue;
}
//源点到源点的距离为0
dis[start] = 0;
//Bellman-Ford算法的核心语句
for(k=1; k<=n-1; k++){
//本轮dis数组是否发生变化
ckeck = 0;
for(i=1; i<=m; i++){
if(dis[v[i]] > dis[u[i]] + w[i]){
dis[v[i]] = dis[u[i]] + w[i];
check = 1;
}
}
//本轮没有发生松弛,则不再继续进行了。
if(ckeck == 0){
break;
}
}
sign = 0
for(i=1; i<=m; i++)
if(dis[v[i]] > dis[u[i]] + w[i])
sign = 1;
if(sign == 1){
printf("此图有负权回路");
}else{
for(i=1; i<=n; i++){
printf("%d ", dis[i]);
}
}
return 0;
}
在第每一轮循环中,其实只对上一次发生了松弛的边的相邻边判断是否需要松弛,因此,没有必要每次都进行m次循环(遍历所有的边判断是否需要松弛)。比如第一轮松弛了1->2和1->5,那么第二次仅仅判断2->3和5->4这两个边是否需要松弛,而不需要遍历所有的边。
在这种情况下,我们引入队列,将需要松弛的点加入队列。每个点仅仅需要入队一次即可,因为入队多次是没有意义的。初始时我们将1号点(源点)加入队列。然后开始遍历队列,对队列中每个点的边进行松弛。队列为空时所得结果便是一个点到其他所有点的最短路径。这是对上述的Bellman-Ford算法一种极大的优化。当然,在最坏的情况下,和Bellman-Ford算法的时间复杂度是一样的,即O(MN)。此优化也可以解决负权边。
完整代码如下:
#include <stdio.h>
int main(){
int dis[10] = {0}, i, j, k, m, n, u[10], v[10], w[10];
int book[10] = {0};
//first数组和next数组用来建立领接表,即first记录一个边的开头,比如第2号边的开头是点a,那么first[a]=2,a开头的下一个边是第5号边,则next[5]=a,组成一个链表的形式
int first[10], next[10];
int queue[100] = {0}, head = 1, tail = 1;
int maxValue = 9999;
//源点为1
int start = 1;
//读入点的个数n,边的个数m
scanf("%d %d", &n, &m);
//初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大
//book用来标记那个点已经入队了,因为队列中同时出现同一个点多次是没有意义。
//first用来标记第i条边的起点
for(i=0; i<=n; i++){
dis[i] = maxValue;
book[i] = 0;
first[i] = -1;
}
//源点到源点的距离为0
dis[start] = 0;
//读入边
for(i=1; i<=m; i++){
scanf("%d %d %d", &u[i], &v[i], &w[i]);
//使用first和next两个数组建立领接表
next[i] = first[u[i]];
first[u[i]] = i;
}
//源点入队
queue[tail] = start;
tail++;
//标记已经入队的点
book[i] = start;
while(head < tail){
//当前需要处理的点,是队首的点,处理队首开头的所有边
k = first[queue[head]];
//扫描这个点开头的所有边
while( k != -1){
if(dis[v[k]] > dis[u[k]] + w[k]){
dis[v[k]] = dis[u[k]] + w[k];
if(book[v[k]] == 0){
queue[tail] = v[k];
tail++;
book[v[k]] = 1;
}
}
k = next[k];
}
//这个点开头的所有边都处理完了,就出队
book[queue[head]] = 0;
head++;
}
for(i=1; i<=n; i++){
printf("%d ", dis[i]);
}
getchar();getchar();
return 0;
}
输入:
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
//输出:
0 -3 -1 2 4
Ps:本算法参考《啊哈!算法》一书。