图详解第五篇：单源最短路径--Bellman-Ford算法

Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而bellman—ford（贝尔曼-福特）算法可以解决负权图的单源最短路径问题，那这篇文章我们就来学习一下Bellman-Ford算法

单源最短路径–Bellman-Ford算法

1. 算法思想

Bellman-Ford是一种比较暴力的求解更新：

它对图进行 V-1 次迭代（其实是最多V-1次，至于为什么是V-1次后面会解释到），其中 V 是图中顶点的数量。
在每次迭代时，遍历图中的所有的顶点，并对每个顶点的相邻顶点进行松弛操作，松弛我们上一篇文章解释过了，即对当前顶点的每一个相邻结点v ，判断源节点s到当前结点u 的代价与u 到v 的代价之和是否比原来s 到v 的代价更小，若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和，否则维持原样，从而不断更新每个顶点的最短路径。
当然如果某次迭代之后不在有新的距离更新，也可以提前结束，这个我们在后面的优化会提到。

贝尔曼-福特算法与迪杰斯特拉算法类似：

都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。
只不过迪杰斯特拉算法每次去选到起点最短的边，然后去向外扩展更新（即对这条边的终止顶点进行松弛），直至所有的边都更新一遍就可以得到结果（因为它每次选的都是最小的）；
而贝尔曼-福特算法不管边的大小，就是比较暴力的把所有的边都更新（即先后对所有的顶点的相邻顶点进行松弛），也因此它一遍过后可能得不出最短的路径，可能需要进行多次迭代。

它的优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。
它也有明显的缺点，它的时间复杂度 O(N*E) (N是点数，E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里如果我们使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是O(N^3)。

2. 图解

那下面我们还是对照着图再给大家走一遍Bellman-Ford算法的过程

就以这个图为例，我们来走一遍整个过程，当然上面这个图可能没有每一步都画出来，不是特别详细

那我们来走一个详细的：

这是起始状态，s位为源点
那首先对s的相邻顶点进行松弛（当然实际中应该是按照顶点在邻接矩阵里面存储的顺序去遍历的，那其实这个图和我们上一篇文章讲Dijkstra算法的那个图顶点都是一样的，只是权值不同，所以下面我们就按之前的存储顺序去走）
那s的话这里他连出去的两条边肯定都会更新（因为源节点s到当前结点u（这里就是s) 的代价与u 到v 的代价之和是否比原来s 到v 的代价更小）
那第一次松弛之后就是这样：

那然后对y的相邻顶点进行松弛

接着是z

z只连出去一条边z->x，但是这里不会更新，因为s->z+z->x的距离大于目前s->x的距离
接着是t

t连出去了两条t->z和t->x，只更新t->z，那之前的s->y->z(16)就不再是z目前的最短路径了（当然实际写代码中的话我们的两个数组：路径距离/权值的数组dist 和 存储路径的数组pPath就也需要相应的修改）
最后是x

x只连出去一条边x->t，进行更新

那现在其实一趟迭代就完成了，所有顶点的相邻顶点都完成了一次松弛

我们现在得到的是这样一个样子：

其实就是最开始给大家看的图里面倒数第二个

可是最后一幅才是最终结果啊：

是的，所以我们上面也说了：
Bellman-Ford算法是比较暴力的把所有的边都更新（即先后对所有的顶点的相邻顶点进行松弛），而不像Dijkstra算法的贪心那样每次选的都是最短的，也因此它一遍过后可能得不出最短的路径，可能需要进行多次迭代

那我们就继续进行第二遍迭代：

第二遍起始状态就是这样的
首先第一个还是s顶点，那这里没有边需要更新；
然后是y，也没有边更新；
接着z，也没有更新；
再下面t，更新一条：现在t的最短路径是2，t->z是-4，所以z的最短路径更新为-2

我们看到这次边并没有变化，只是权值更新了；
因为上一轮z的最短路径确定为s->t->z：2（此时t的最短路径是s->t：6）之后，t的最短路径又被更新成了s->y-x-t：2
t的最短路径变了，导致z的最短路径也变了，但是在第二轮才更新出来
最后顶点x，也没有边更新

此时就得到了最终结果，所以我们看到这里这个图起始更新了两轮（后面代码写出来我们也可以验证一下是不是两轮）就得到了最终结果，后续即使再进行迭代，也不会有新的路径更新了。
所以我们说了可以提前结束，不一定非要迭代V-1 次， V 是图中顶点的数量

那我们也来说一下，为什么最多要迭代V-1次呢？

因为如果一个图有V个顶点，那图中路径最多也只经过V-1条边，所以V-1次迭代可以保证所有顶点的最短路径被正确地计算更新。
当然我们可以通过判断提前结束。

3. 代码实现

那下面我们就来写写代码：

首先前面的部分和Dijkstra算法是一样的
我就不过多解释了
那然后我们就迭代更新就行了

4. 测试

来测试一下：

这个测试用例就是我们上面讲解的时候用的图，来看一下对不对

对照一下

没有问题

我们还可以验证一下是不是更新了两轮就完成了：

加个打印看一下

再来运行

没有问题，只有前两轮有更新，而且大家可以对照一下，更新的边跟我们上面分析的都是一致的

5. 优化

循环的提前跳出

首先第一个优化就是我们上面提到的：

Bellman-Ford算法最多对图进行V-1次迭代，但是如果某次迭代之后不在有新的距离更新，我们就可以提前结束循环。

那这个优化很好做到：

在循环中设置一个判定就行了

队列优化

西南交通大学的段凡丁于1994年提出了用队列来优化的算法：

松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上。
通过使用队列来存储需要进行松弛操作的顶点，可以减少不必要的重复操作。在每次迭代中，只需要对队列中的顶点进行松弛操作，而不用遍历整个图。

解释一下：

就比如我们上面那个图的例子，它其实只有前两轮进行了更新，而且第二轮的时候只对结点t进行了松弛更新

为什么呢？
因为第一轮t的最短路径更新为s->t(6)之后，后面又变成了s->y-x-t(2)

那它就可能影响它的相邻顶点的最短路径

而除了t之外的其它顶点第二轮并没有真正松弛更新，虽然进行了判断

所以就可以进行队列优化：

搞一个队列，第一轮让所有顶点都入队列，第二轮就只让第一轮更新出更短路径的顶点入队列（后续也是如此），只对队列中的顶点进行松弛操作，就可以避免冗余计算。

那这个优化大家有兴趣可以自己实现一下

6. 负权回路（负权环）判定

那除此之外呢还有一个问题：

虽然Bellman-Ford算法可以解决负权图的单源最短路径问题，但是对于图中有负权回路/环（即图中存在环/回路，且环的权值之和为负值）的情况，Bellman-Ford算法也无能为力，这种情况是求不出最短路径的！

因为如果有负权环的话，某些顶点的最小路径是可以一直往小去更新的：

比如

s->y的距离，如果走s->t->y的话是-2，但是如果从y再顺时针绕一圈就变成-3了，再绕就是-4，可以一直减小，无限制的降低总代价。
当然现在这个图里不止这一个负权环。

我们可以来测试一下：

这个测试用例其实就对应上面的图
运行一下

当然这里我们外层循环直接控制了它最多迭代n-1次（n为顶点个数），所有这里迭代n-1次就停了。
但是要注意这里的结果是不对的，因为如果我们让它继续迭代的话，有些路径是可以继续缩小的。
如果我们不控制外层循环的话，它应该就要死循环的迭代更新了

而且我们把打印放开的话会看到他这里就找路径的时候就死循环卡在这里了

大家可以调式观察一下，肯定就是往上找路径的时候陷入到环里面了

那我们可以想办法检测一下这种情况：

其实很好办：
如果在进行了n-1次迭代之和还能更新，就是带负权回路的情况
因为如果不带负权回路的情况，最多迭代n-1次就可以得到最终结果

这样我们就可以通过返回值判断是否带负权环

测试一下：

就判断出来了
如果还把图改回原来的

没问题！

7. 源码

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
{
	//初始化一下记录路径和权值（距离）的数组
	size_t srci = GetVertexIndex(src);
	size_t n = _vertexs.size();
	pPath.resize(n, -1);
	dist.resize(n, MAX_W);

	pPath[srci] = srci;
	dist[srci] = W();

	//最多迭代n-1次
	for (size_t k = 0; k < n - 1; k++)
	{
		//一趟迭代的逻辑
		cout << "第" << k + 1 << "轮迭代：" << endl;
		bool update = false;
		//依次遍历所有顶点
		for (size_t i = 0; i < n; i++)
		{
			//对每个结点的相邻顶点进行松弛操作
			for (size_t j = 0; j < n; j++)
			{
				if (_matrix[i][j] != MAX_W
					&& dist[i] + _matrix[i][j] < dist[j])
				{
					update = true;
					cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
					dist[j] = dist[i] + _matrix[i][j];
					//同时更新记录路径的数组pPath
					pPath[j] = i;
				}
			}
		}

		if (update == false)
			break;
	}

	//如果进行了n-1次迭代之和还能更新，就是带负权回路的情况
	for (size_t i = 0; i < n; i++)
	{
		//对每个结点的相邻顶点进行松弛操作
		for (size_t j = 0; j < n; j++)
		{
			if (_matrix[i][j] != MAX_W
				&& dist[i] + _matrix[i][j] < dist[j])
			{
				return false;
			}
		}
	}

	return true;
}
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

void TestGraphBellmanFord()
{
	/*const char* str = "syztx";
	Graph<char, int, INT_MAX, true> g(str, strlen(str));
	g.AddEdge('s', 't', 6);
	g.AddEdge('s', 'y', 7);
	g.AddEdge('y', 'z', 9);
	g.AddEdge('y', 'x', -3);
	g.AddEdge('z', 's', 2);
	g.AddEdge('z', 'x', 7);
	g.AddEdge('t', 'x', 5);
	g.AddEdge('t', 'y', 8);
	g.AddEdge('t', 'z', -4);
	g.AddEdge('x', 't', -2);
	vector<int> dist;
	vector<int> parentPath;
	g.BellmanFord('s', dist, parentPath);
	g.ptintMinPath('s', dist, parentPath);*/

	const char* str = "syztx";
	Graph<char, int, INT_MAX, true> g(str, strlen(str));
	g.AddEdge('s', 't', 6);
	g.AddEdge('s', 'y', 7);
	g.AddEdge('y', 'z', 9);
	g.AddEdge('y', 'x', -3);
	//g.AddEdge('y', 's', 1); // 新增
	g.AddEdge('z', 's', 2);
	g.AddEdge('z', 'x', 7);
	g.AddEdge('t', 'x', 5);
	//g.AddEdge('t', 'y', -8); // 更改
	g.AddEdge('t', 'z', -4);
	g.AddEdge('x', 't', -2);

	vector<int> dist;
	vector<int> parentPath;
	if (g.BellmanFord('s', dist, parentPath))
		g.ptintMinPath('s', dist, parentPath);
	else
		cout << endl << "带负权回路!!!" << endl;
}
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