SPFA算法以及负环判断【模板】
标签：邻接表 方式 队列 using color 形式 include bre ios
算法简述
SPFA算法其实是bellman-ford算法的队列优化形式，不再是简简单单的进行n-1次松弛，而是使用队列，能使路径变短（dist[y] > dist[x] + 1）且不在队列里的节点才入队进行松弛。
SPFA算法与Dijkstra算法的堆优化实现形式差不多，都是使用邻接表的方式。
代码
#include
#include
#include
#include#define maxn 1000002
#define maxm 2000002
#define inf 0x3f3f3f3f
using namespace std;
struct edge
{
int to;
int next;
int dis;
}e[maxm];
int head[maxn], dist[maxn], cnt, visited[maxn];
int n, m;
void addedge(int u, int v, int w)
{
cnt++;
e[cnt].to = v;
e[cnt].dis = w;
e[cnt].next = head[u];
head[u] = cnt;
}
queueint>q;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i )
{
int a, b;
scanf("%d%d", &a, &b);
addedge(a, b, 1);
addedge(b, a, 1);
}
fill(dist, dist + n + 1, inf);
dist[1] = 0;
visited[1] = 1;
q.push(1);
while (!q.empty())
{
int x = q.front(); q.pop();
visited[x] = 0;//这里将visited[x]置为0，防止下面干扰能使路径变短（dist[y] > dist[x] + 1）且不在队列里的节点的判断
for (int i = head[x]; i; i = e[i].next)
{
int y = e[i].to;
if (dist[y] > dist[x] + 1)//能使路径变短（dist[y] > dist[x] + 1）且不在队列里的节点才入队
{
dist[y] = dist[x] + 1;
if (!visited[y])//节点重复入队是没有意义的！！
{
q.push(y);
visited[y] = 1;
}
}
}
}
}
判断负环
我们用 counts[i] 表示从起点（假设就是 1）到 i 的最短距离包含点的个数，初始化 counts[1] = 1，
那么当我们能够用点 u 松弛点 v 时，松弛时同时更新 counts[v] = counts[u] + 1，若发现此时 counts[v] > n，那么就存在负环
代码
#include
#include
#include
#include#define maxn 1000002
#define maxm 2000002
#define inf 0x3f3f3f3f
using namespace std;
struct edge
{
int to;
int next;
int dis;
}e[maxm];
int head[maxn], dist[maxn], cnt, visited[maxn], counts[maxn];
int n, m;
void addedge(int u, int v, int w)
{
cnt++;
e[cnt].to = v;
e[cnt].dis = w;
e[cnt].next = head[u];
head[u] = cnt;
}
queueint>q;
int main()
{
bool isnegative = false;
scanf("%d%d", &n, &m);
for (int i = 0; i )
{
int a, b;
scanf("%d%d", &a, &b);
addedge(a, b, 1);
addedge(b, a, 1);
}
fill(dist, dist + n + 1, inf);
dist[1] = 0; counts[1] = 1;
visited[1] = 1;
q.push(1);
while (!q.empty())
{
int x = q.front(); q.pop();
visited[x] = 0;//这里将visited[x]置为0，防止下面干扰能使路径变短（dist[y] > dist[x] + 1）且不在队列里的节点的判断
for (int i = head[x]; i; i = e[i].next)
{
int y = e[i].to;
if (dist[y] > dist[x] + 1)//能使路径变短（dist[y] > dist[x] + 1）且不在队列里的节点才入队
{
dist[y] = dist[x] + 1;
counts[y] = counts[x]+1;
if (counts[y] > n) { isnegative = true; break; }
if (!visited[y])//节点重复入队是没有意义的！！
{
q.push(y);
visited[y] = 1;
}
}
}
}
if (isnegative) printf("Yes\n");//存在负环
else printf("No\n");
}
SPFA算法以及负环判断【模板】
标签：邻接表 方式 队列 using color 形式 include bre ios
原文地址：https://www.cnblogs.com/Jason66661010/p/12901888.html
评论