Bellman-Ford 算法

缘起

【1】【2】分别给出了有向非负权网的最短路径的算法，前者是图中任意两点的. 后者是单源的. 但是不论是floyd还是dijkstra，都要求不含负权边. 那么对于含有负权边有什么办法求出最短路径呢? bellman-ford就此诞生. 该算法不仅可以求出可能含有负权边的有向图单源最短路径，或者如果存在负权环的导致不存在最短路径则能检测出来.

分析

注意到两点之间的最短路径中最多n-1条弧(否则，出现环，但是如果是正权环的话，则可以减少弧的数量使得路径长度降低，如果是负权环的话,就不会是最短路径,因为可以不挺的绕啊，绕啊，绕啊，导致不是最短路)
所以如果能求出最短路的话,一定在n-1轮中结束战斗。

如果令dis[k][i]表示单源（这里是写死的1号顶点）到顶点i的可以通过不超过k条边达到的最短路径.

则dp模型是 对于固定的 1<=k<n(即n-1轮dp)

1
dis[k][i]=min{dis[k-1][i],dis[k-1][j]+<j,i>的权重},其中j的取值范围是弧j->i存在

利用滚动数组我们可以很方便的得到如下算法

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
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)

#define LOCAL
using namespace std;
const int MAX_V_NUM = 20;
const int MAX_E_NUM = 20;
const int INF = 0x3f3f3f3f;

struct Graph
{
	int n,m; // n是实际顶点的个数，m是实际边的条数
	
	struct Edge
	{
		int x,y,w;
	};

	Edge edges[MAX_E_NUM];

	int distance[MAX_V_NUM]; // distance[i] 表示到顶点i到单源1（这里源写死了, 就是1）的最短距离, 显然 distance[1]=0;

	Graph()
	{
		puts("输入顶点的个数和边的条数");
		scanf("%d%d", &n, &m);
		puts("输入边的起点, 终点, 权重.");
		for (int i = 1;i<=m;i++) scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
	}
	
	bool bellman_ford() // bellman-ford算法
	{
		memset(distance, 0x3f, sizeof(distance));
		distance[1] = 0;
		bool isok;
		int i,j;
		for (i = 1; i<=n;i++) // n-1轮dp + 1轮负权环检测  bellman_ford算法的核心
		{
			isok = true;
			for (j = 1; j<=m;j++) // 遍历所有的边
			{
				if (distance[edges[j].y] > distance[edges[j].x]+ edges[j].w)
				{
					distance[edges[j].y] = distance[edges[j].x]+ edges[j].w;
					isok = false;
				}
			}
			if (isok) break; // 不再进行松弛
		}
		if (!isok) return true; // 如果经过了上面n-1轮松弛, 还是不ok的话, 则表明有负权环
		for (int i = 2; i<=n; i++) printf("单源1到%d的最短距离是%d\n", i, distance[i]);
		return false;
	}

};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	if (g.bellman_ford())
	{
		puts("存在非负权环. 不存在最短路径");
	}
	return 0;
}
/*
测试数据
5 5
1 2 -3
2 3 2
3 4 3
4 5 2
1 5 5
*/

显然, bellman-ford算法的复杂度是 O(nm), n是顶点的个数，m是边的条数

参考

【1】https://yfsyfs.github.io/2019/05/27/floyd%E7%AE%97%E6%B3%95/

【2】https://yfsyfs.github.io/2019/05/27/dijkstra%E7%AE%97%E6%B3%95/