最短路算法-spfa判断负环
in Algorithm Pageviews
单源最短路径。边的权值为负数,可以使用SPFA来判断负是否存在负环
SPFA判断负环
使用场景:
- 所有边的权值可能为负值
- 判断是否存在负权回路
题目举例:
给定n
个顶点,m
条边的有向图,图中可能存在重边或者自环,边的权重可能为负数;判断图中是否存在负权回路。
#include <bits/stdc++.h>
constexpr int N = 10010;
int h[N];
int w[N];
int e[N];
int ne[N];
int idx = 0;
int dist[N];
int vis[N];
int cnt[N];
using namespace std;
// 模拟邻接表
void add(int a, int b, int w)
{
e[idx] = b;
w[idx] = w;
ne[idx] = h[a];
h[a] = idx++;
}
bool spfa()
{
queue<int> que;
memset(dist, 0x3f, sizeof(dist));
for (int i = 1; i <= n; i++) {
que.push(i);
vis[i] = true;
}
while (!que.empty()) {
auto t = que.front();
que.pop();
vis[t] = false;
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 true;
}
if (!vis[j]) {
que.push(j);
vis[j] = true;
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 0; i < m; i++) {
int a = 0, b = 0, w = 0;
cin >> a >> b >> w;
add(a, b, w);
}
cout << spfa();
return 0;
}