bellman-ford算法之队列优化

缘起

【1】中我们给出了单源可能带负权环的有向网的最短路径算法——bellman-ford算法. 但是观察其复杂度，是O（NM）的. 较高, 那我们想想看，是不是有什么地方值得优化呢?

分析

显然, 如果一个顶点已经到达了其到达单源的最短路径的话, 它是无法通过它出发的边对其他顶点进行松弛的. 所以我们不需要考察这种点. 所以我们可以维护一个队列，队列中放置本轮松弛的确松弛了的顶点进去. 因为只有本轮到达单源的最短路径值发生了变化, 它在下一轮dp的时候才可能通过它出发的边去松弛别的顶点. 所以这个队列中只需要存放被松弛的顶点. 而【1】中之所以复杂度高, 是因为每次dp的时候, 一些已经到达最短距离的顶点还在考察(其实没必要考察了)

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
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
#include <vector>
#include <queue>
#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; // n是实际顶点的个数

	struct Edge
	{
		int v,w;
		Edge(int v, int w):v(v),w(w){}
	};
	
	vector<Edge> vertex[MAX_V_NUM]; // 邻接链表法

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

	Graph()
	{
		puts("输入顶点的个数和边的条数");
		scanf("%d", &n);
		puts("输入边的起点, 终点, 权重.");
		int x,y,w;
		while(~scanf("%d%d%d", &x,&y, &w)) vertex[x].push_back(Edge(y,w));
	}
	
	bool bellman_ford() // 使用队列优化的bellman_ford算法
	{
		memset(distance, 0x3f, sizeof(distance));
		distance[1] = 0;
		int count[MAX_V_NUM]; // 每个顶点进入队列的次数, 它用于判定是否存在负权环
		memset(count,0,sizeof(count));
		bool book[MAX_V_NUM]; // true 表示在队列中, false表示不在队列中
		memset(book, 0, sizeof(book)); // 是否在队列中
		queue<int> q; // q中只存储发生松弛的点
		q.push(1);
		count[1] = 1;
		book[1] = true;
		while(!q.empty())
		{
			int front = q.front();
			q.pop();
			book[front] = false; // 出队了, 不再在队列中了
			for (it x = vertex[front].begin(); x!=vertex[front].end(); x++)
			{
				if (distance[front]+x->w<distance[x->v]) // 如果可以发生松弛
				{
					distance[x->v] = distance[front]+x->w; // 松弛之
					if (!book[x->v]) // 如果已不在队列中的话
					{
						book[x->v] = true;
						if (++count[x->v] == n) return false; // 进队一次, 如果某个顶点累计进队次数达到了n次的话, 则表明它至少会被松弛n次. 但是其实最多n-1条边就要到达最短路径的, 说明一定存在负权环
						q.push(x->v);
					}
				}
			}
		}
		for (int i = 1; i<=n; i++) printf("单源1到达%d的最短距离是%d\n", i, distance[i]);
		return true;
	}

};


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

注意, 一个点是可能重复进队列的, 因为可能伊始不能被松弛，但是有新的点的distance变化之后, 这个点就能被松弛了. 然后后面又有一个点变化了, 它会再次被松弛.

参考

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