Spfa求最短路
https://www.acwing.com/problem/content/853/
St
数组在这里的意义跟之前的不同,之前表示是否已经找到最短路的状态,而SPFA
中表示是否在队列中。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int e[N], h[N], ne[N], w[N], idx, dist[N], st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa() {
queue<int> q;
q.push(1);
st[1] = 1;
while (q.size()) {
int t = q.front(); q.pop();
st[t] = 0;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
q.push(j);
st[j] = 1;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) cout << "impossible\n";
else cout << dist[n] << endl;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof(h));
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
spfa();
}
- SPFA是对Bellman-Ford的优化:
- Bellman-Ford用两重循环有很多无效循环,而
SPFA
只会通过dist
变小过的节点去更新别的节点的dist
。 -
也就是把更新过
dist
的节点入队,然后把这些节点邻接的点的dist
更新一遍。 -
检查终点是否可达:
- 最后检查
if (dist[n] == 0x3f3f3f3f)
就行。 - 虽然有负权边,但不用
if (dist[n] > 0x3f3f3f3f / 2)
这样检查。 - 因为如果起点到不了终点,那么就算存在终点邻接的节点,权值为负,这个节点也不会入队(因为它跟起点不连通),
dist
不会被更新,所以终点为0x3f3f3f3f
也不会被减去2。
Spfa找负环
https://acwing.com/problem/content/854/
大体上与SPFA
找最短路的代码一样。
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 2010, M = 10010;
int h[N],e[M],ne[M],w[M],idx,dist[N],cnt[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa() {
queue<int> q;
for(int i = 1; i <= n; i++) {
q.push(i);
st[i] = 1;
}
while(q.size()) {
int t = q.front();
q.pop();
st[t] = 0;
for(int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if(dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) {
return 1;
}
if(!st[j]) {
st[j] = 1;
q.push(j);
}
}
}
}
return 0;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if(spfa()) cout << "Yes" << endl;
else cout << "No" << endl;
}
- 增加
cnt
数组记录松弛次数: - 加一个
cnt
数组,用于记录这个节点被松弛了多少次(也就是dist
被更新了几次)。 - 如果图中没有负环,一个节点的
cnt
最多是n - 1
(因为一共n
个点,其他点都跟他有边就会是n - 1
)。 -
但是如果有负环,一旦
SPFA
来到负环,就会一直在这里转圈(因为负环转一圈,dist
就会变少,永远会在负环这里更新),所以负环上的节点会无限地入队,dist
会无限更新,cnt
会无限增加,直到cnt >= n
了,就说明存在负环。 -
dist
数组的初始化: - 这里的
dist
数组不需要初始化成0x3f
。 -
因为这个算法不需要找最短路,只需要判断是否存在负环。所以所有的正权边对找负环没有影响,他们的
cnt
没有用,只有碰到负环的时候,cnt
才会不断增加,直到>= n
。 -
初始时将所有节点入队:
SPFA
最开始要把所有的节点都入队,因为负环可能跟起点不连通,所以干脆直接都入队。- 因此,找负环的时间复杂度相对较高。