SPFA 算法模板

SPFA 代替 Dijkstra 计算最短路 题目

题目链接

题解

SPFA 一般时间复杂度为 O ( m ) O(m) O(m)，最坏情况下为 O ( n m ) O(nm) O(nm)，本质是对 Bellman_ford 算法的优化。可以用于计算正、负边权的最短路，但不能取代 Bellman_ford 计算有步数限制的最短路。单源最短路问题。

思想：

在Bellman_ford算法中需要遍历全部的边来更新最短路，但是 d[b] = min (d[b], d[a] + w) 只有在 d[a] 被更新（变小），d[b]才有可能变小，所以我们试图将变小的d[b]对应的b记录下来，只用这些点去更新最短路。在用这些点更新的过程中再有被更新点就再记录下来。

代码

#include
using namespace std;

const int N = 1e4+10, M = 5e5+10, INF = 0x3f3f3f3f;

int d[N];
bool st[N];
int w[M], e[M], ne[M], h[N], idx;
int n, m, s;

void add (int a, int b, int c) {
	w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void spfa () {
	
	memset (d, 0x3f, sizeof d); // !!!
	d[s] = 0;
	
	queue  q;
	q.push (s);
	st[s] = true; // 表示 s 是否在队列中，在队列中就不要重复插入了 
	
	while (!q.empty ()) {
		int t = q.front ();
		q.pop ();
		st[t] = false;
		for (int i = h[t];~i;i = ne[i]) {
			int j = e[i];
			if (d[j] > d[t] + w[i]) {
				d[j] = d[t] + w[i];
				if (!st[j]) 
					q.push (j),
					st[j] = true; // !!
			}
		}
	}
}

int main() {
	memset (h, -1, sizeof h); // !!!
	
	cin >> n >> m >> s;
	for (int i = 1;i > a >> b >> c;
		add (a, b, c);
	}
		
	spfa ();
	
	for (int i = 1;i  m;
	for (int i = 0;i > a >> b >> c;
		add (a, b, c);
	}

	if (spfa ()) puts ("Yes");
	else puts ("No");
	
	return 0;
}

SPFA 判断是否存在以某一点为起点的负环 题目

题目链接

代码

#include
using namespace std;

const int N = 2e3+10, M = 1e6+10; // 题目中m的数据范围并非边的上限 ！！！因为存在回边 

int n, m;
int idx, e[M], ne[M], w[M], h[N];
bool st[N];
int d[N], cnt[N];

void add (int a, int b, int c) {
	w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool spfa () {
	// 注意很多初始化 
	memset (cnt, 0, sizeof cnt);
	memset (d, 0x3f, sizeof d);
	memset (st, false, sizeof st);
	d[1] = 0; // 本题起点确定，所以需要初始化 
	
	queue  q;
	q.push (1);
	st[1] = false;
	
	while (!q.empty ()) {
		int t = q.front ();
		q.pop ();
		st[t] = false;
		
		for (int i = h[t]; ~i;i = ne[i]) {
			int j = e[i];
			if (d[j] > d[t] + w[i]) {
				d[j] = d[t] + w[i];
				
				cnt[j] = cnt[t] + 1;
				if (cnt[j] >= n) return true;
				
				if (!st[j]) {
					q.push (j);
					st[j] = true;
				}
			}
		}
	}
	return false;
}

int main()
{
	int T;
	cin >> T;
	while (T--) {
		memset (h, -1, sizeof h); // 注意初始化
		idx = 0; // 注意初始化 
		cin >> n >> m;
		while (m --) {
			int a, b, c;
			cin >> a >> b >> c;
			add (a, b, c);
			if (c >= 0) add (b, a, c);
		}
		
		if (spfa ()) cout