Introduction of SPFA and application of negative judgment ring
SPFA (queue optimization algorithm) is an algorithm for finding the shortest path of a single source. Another important function of SPFA is to judge the negative loop.
If it is not necessary to judge the negative ring, Dijkstra is recommended
Main ideas and methods:
Set an array to store the shortest path (the current optimal solution in the process) from the source point to other vertices. During initialization, other vertices are infinite.
Set up another queue, read the vertex of the queue head, and add the vertex of the queue head n o w now now out of the line (remember to eliminate the mark), will be with the point n o w now All points connected by now n e x t next next, perform the relaxation operation. If the value can be updated (i.e d i s [ n e x t ] > d i s [ n o w ] + v a l u e [ n o w ] [ n e x t ] dis[next]>dis[now]+value[now][next] Dis [next] > dis [now] + value [now] [next]), then update. In addition, if point n e x t next next has no points in the queue to add n e x t next next join the queue. If you are already in the queue, you don't need to join the queue.
This loop completes the solution of the single source shortest path until the queue is empty.
Interpretation of judging negative rings
If there is a negative ring in the graph, when we traverse this ring, the value of the shortest path is always decreasing, and we are trapped in this dead cycle. In other words, 1 1 1 to x x The number of shortest sides of x must not be more than n − 1 n-1 n−1 . Otherwise, at least one node is repeated, which indicates that there is a ring. If it passes through the ring, the relaxation operation can still be updated d i s dis dis value, that is, there is a negative ring.
Implementation method of judging negative ring
Bellman Ford judgment negative ring
Bellman Ford algorithm calculates the shortest path through continuous iteration, and at least one node gets the shortest path in each iteration. Therefore, if there is no negative ring in the graph, it passes through at most n − 1 n-1 After n − 1 round of iteration, the algorithm ends. If the first n n If the shortest path of the node can be updated in n rounds of iteration, there is a negative ring in the graph.
SPFA judgment negative loop
SPFA is Bellman Ford for queue optimization, so we can judge the negative ring by analogy with Bellman Ford. However, SPFA uses queues and cannot directly know which iteration is in progress. Looking at Bellman Ford, we find that i i Round i iteration is actually calculating the shortest path inclusion i i i is the node of the edge. So we use c n t [ x ] cnt[x] cnt[x] indicates 1 1 1 to x x The number of sides included in the shortest path of x, $cnt[1]=0 $. Update every slack operation d i s [ y ] dis[y] dis[y] c n t [ x ] + 1 cnt[x]+1 cnt[x]+1 update c n t [ y ] cnt[y] cnt[y] . During this process, if c n t [ y ] ≥ n cnt[y]\geq n cnt[y] ≥ n, then there is a negative ring in the graph.
realization
Template questions: delivery
#include<bits/stdc++.h>
using namespace std;
#define MAXN 2005
#define MAXM 200005
#define ll long long
ll dis[MAXN];//Storage shortest path
ll cnt[MAXN];//Number of storage edges
ll n,m;
int visit[MAXN];
struct node
{
int to,next,val;
}edge[MAXM];
int head[MAXM];
int tot=0;
void add_edge(int from,int to,int val)
{
edge[++tot].to=to;edge[tot].val=val;edge[tot].next=head[from];head[from]=tot;
}
void init()
{
tot=0;
for(int i=1;i<=n;i++)
{
visit[i]=0;
head[i]=0;
dis[i]=0x3f3f3f3f;
cnt[i]=0;
}
}
void build()
{
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
if(w<0)
{
add_edge(u,v,w);
}
else
{
add_edge(u,v,w);
add_edge(v,u,w);
}
}
}
bool spfa(int s,int n)//Number of source points and nodes
{
dis[s]=0;
queue <int> q;
q.push(s);
visit[s]=1;
while(!q.empty())
{
int now=q.front();q.pop();
visit[now]=0;
for(int i=head[now];i;i=edge[i].next)
{
int next=edge[i].to;
int val=edge[i].val;
if(dis[now]+val<dis[next])
{
dis[next]=dis[now]+val;
cnt[next]=cnt[now]+1;
if(cnt[next]>=n) return 0;
if(visit[next]==0)
{
visit[next]=1;
q.push(next);
}
}
}
}
return true;
}
void solve()
{
cin>>n>>m;
init();
build();
bool flag=spfa(1,n);
if(flag==0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
Judgment method 2
We can also judge the negative loop by recording the number of times of joining the team at each point. If the queue number of a node reaches n times, it indicates that there is a negative ring in the graph and there is no shortest path.
#include<bits/stdc++.h>
using namespace std;
#define MAXN 2005
#define MAXM 200005
#define ll long long
ll dis[MAXN];//Storage shortest path
ll cnt[MAXN];//Store queue times
ll n,m;
int visit[MAXN];
struct node
{
int to,next,val;
}edge[MAXM];
int head[MAXM];
int tot=0;
void add_edge(int from,int to,int val)
{
edge[++tot].to=to;edge[tot].val=val;edge[tot].next=head[from];head[from]=tot;
}
void init()
{
tot=0;
for(int i=1;i<=n;i++)
{
visit[i]=0;
head[i]=0;
dis[i]=0x3f3f3f3f;
cnt[i]=0;
}
}
void build()
{
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
if(w<0)
{
add_edge(u,v,w);
}
else
{
add_edge(u,v,w);
add_edge(v,u,w);
}
}
}
bool spfa(int s,int n)//Number of source points and nodes
{
dis[s]=0;
queue <int> q;
q.push(s);
visit[s]=1;
while(!q.empty())
{
int now=q.front();q.pop();
visit[now]=0;
for(int i=head[now];i;i=edge[i].next)
{
int next=edge[i].to;
int val=edge[i].val;
if(dis[now]+val<dis[next])
{
dis[next]=dis[now]+val;
if(visit[next]==0)
{
cnt[next]++;
if(cnt[next]>=n) return 0;
visit[next]=1;
q.push(next);
}
}
}
}
return true;
}
void solve()
{
cin>>n>>m;
init();
build();
bool flag=spfa(1,n);
if(flag==0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}