算法分析
使用spfa算法解决是否存在负环问题
求负环的常用方法，基于SPFA，一般都用方法 2（该题也是用方法 2）：
- 方法 1：统计每个点入队的次数，如果某个点入队
n次，则说明存在负环 - 方法 2：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于
n，则也说明存在环
y总的原话
每次做一遍spfa()一定是正确的，但时间复杂度较高，可能会超时。初始时将所有点插入队列中可以按如下方式理解：
在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa，将虚拟源点加入队列中。然后进行spfa的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。执行到这一步，就等价于视频中的做法了。那么视频中的做法可以找到负环，等价于这次spfa可以找到负环，等价于新图有负环，等价于原图有负环。得证。
-
1、
dist[x]记录虚拟源点到x的最短距离 -
2、
cnt[x]记录当前x点到虚拟源点最短路的边数，初始每个点到虚拟源点的距离为0，只要他能再走n步，即cnt[x] >= n，则表示该图中一定存在负环，由于从虚拟源点到x至少经过n条边时，则说明图中至少有n + 1个点，表示一定有点是重复使用 -
3、若
dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少，因此进行对该点j进行更新，并且对应cnt[j] = cnt[t] + 1,往前走一步
注意：该题是判断是否存在负环，并非判断是否存在从1开始的负环，因此需要将所有的点都加入队列中，更新周围的点
时间复杂度 一般：$O(m)$ 最坏：$O(nm)$
参考文献
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int n;
static int m;
static int N = 2010;
static int M = 10010;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] w = new int[M];
static int idx = 0;
static int[] dist = new int[N];//记录虚拟点到x的最短距离
static int[] cnt = new int[N];//从虚拟点到x经过的边数
static boolean[] st = new boolean[N];
public static void add(int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
public static boolean spfa()
{
Queue<Integer> queue = new LinkedList<Integer>();
//将所有点进入队列
for(int i = 1;i <= n;i++)
{
queue.add(i);
st[i] = true;
}
while(!queue.isEmpty())
{
int t = queue.poll();
st[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(!st[j])
{
queue.add(j);
st[j] = true;
}
}
}
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
Arrays.fill(h, -1);
while(m -- > 0)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
int c = Integer.parseInt(str2[2]);
add(a,b,c);
}
if(spfa()) System.out.println("Yes");
else System.out.println("No");
}
}
因为负环的存在，所以即使每个点距离虚拟原点距离为0，负权边的存在依然可以更新某个点为更小的负值
借个楼，请问每个点的入队次数是否有其具体含义，为何能够用入队次数来判断负环
方法 1 的思路是统计每个节点入队的次数。如果某个节点入队的次数超过了图中所有节点的数量 n（图中节点数量记为 V），说明这个节点被入队的次数太多，也就意味着它的最短路径被更新了很多次。由于负环的特性，如果某个节点的最短路径被更新了足够多次，那么就说明从起点到该节点的路径中包含了一个负环，因为在负环中，不断经过环路可以无限次减小路径权重。
虚拟源点，好棒的解释！
我看评论区有的同学说，题中没有说明是连通图，所以才要把所有结点入队，但是我觉得并不是，即便是连通图，也要把所有结点入队才能保证代码正确性。
先举一个简单例子，最开始只把1结点入队，如果1结点不在负权回路中，而且以1结点为起点的边只有一条，而且该边的权重还是正数，那么按照代码逻辑走一边会发现，1结点出队后，没有任何结点入队，那么循环直接停了，此时有负权边也没有找到。
大家可以自己再举例子，然后按照代码逻辑走一遍，我的想法是无论是否连通，都要把所有结点先入队，才可以保证代码正确；仅仅只有一些极端的情况，只入队一个结点可以得到结果，比如图连通，而且负权回路中的所有负权路径都连在一起，这时把这一串负权路径的起点入队，这样代码可以得到正确结果，但是这都是一些个别情况。
理解力
“1结点出队后，没有任何结点入队”这是为啥？如果按照上一题的代码，连通图的所有节点都会入队，因为初始是正无穷
“1结点出队后，没有任何结点入队”这句话要是成立，在这种情况下spfa找最短路径也不工作了。。
y总本题代码默认有个虚拟节点，所以所有的dist = 0 , 所以1节点周围边均是正值时不会在队列加入任何边，程序就会停止。即使有负权环也检测不出。之前那个求最短距离默认dist为无穷大，但是设置了dist[1] = 0 , 这样只要1有临边就会加入新的点，程序会进行下去。当然也是为了防止有多个连通分量。
感谢明白了，解释了为什么dis数组不初始化为正无穷和初始队列为什么要全部结点入队的疑问
错误的，如果把d初始化为较大值，各个点连通的时候不必把所有点入队
赞一个，理解了
一定要将所有点入队我认为是因为图可能会不连通，如果负环是在和1这个点不连通的部分，就无法查到，所以要将所有点都入队
是这样的
好像不是这样的，我只将1点加入到队列里了，然后测示例，发现错了，但是示例的确是一个连通图，我也糊涂了
只在正确代码里改了这一点吗
是的，然后我又初始化了一下所有都边为正无穷，答案此时对了，然后我有尝试了其他不同的连通着的图来测，都没错，这时候我就感觉必须初始化
你说的是对的，博主其实和你一个意思，就是因为没有起点终点，图不一定连通所有点，所有这种做法相当于建立了虚拟源点
跟初始化为多少没有关系，虚拟原点是多少都可以，只要每一个都赋成一样，在一个起跑线上就可以，这个
核心是更新多少次，只要在同一起跑线上，如果有负环更新次数一定大于等于n
所以大佬弄懂为什么不能只加入1点且是连通图的情况吗
构建一个图，先有一个负权环，然后从这个环中每个节点发出边，而没有其他节点能指向这个负权环的任意节点，然后起始节点在这个负权环的外面，因此起始点走不到负权环
既然加上了一个虚拟源点，那么不存在负环的路径最长是不是应该为n？
cnt[j] > n的判断是没有问题的同问
同
并不是，因为在接入虚拟源点的时候并没有将cnt数组更新为1，也就是说在算路径长度的时候并没有算上虚拟源点到原图节点的这一段路径。
为什么原图有负环等价于新图有负环???
我理解 原图有负环可以 推出得到新图有负环
但是在引入这个源点之后 因为和别的顶点的权值都是0 那么只要两个结点之间有负边权 那么这两个点加上引入的源点就可以组成一个负环 但是这个负环是在新图中新出现的 不属于原先的旧图
所以这也就推不出来 新图有负环
所以我觉得这个旧图有负环不能等价于新图有负环
虚拟原点并不能与原图里的点形成负环，因为连接的是一条从虚拟原点到第i个点的边，而不能建立任何一条从第i个点到虚拟原点的边，虚拟原点的入度为0，就不能形成有虚拟原点参与的环（环的每一个点的入度和出度都不为零）
大佬说的正确，这个问题的核心在于这一部分代码
for(int i = 1;i <= n;i++)
{
queue.add(i);
st[i] = true;
}
代码的逻辑是建立由虚拟原点到各个点的有向边（有向边是关键），实现方式是将各个点都进行入队，如果我们将虚拟原点进行入队就代表我们建立了一个由点i到虚拟原点的有向边。
只有当旧图之中存在环，新图之中才能出现环。所以新图有负环能推出旧图负环
大佬，图借我用用哈
我怀疑你在逗小孩子呢hh
为什么数组模拟队列会有些数据过不了
神
问下，怎么改，可以找出有几个负环
nb太nb了
有大佬能解释一下为什么不能按上题那样只入队结点1吗？我还是没懂，连通图的情况下，1能到所有节点，也就是负环确实一直会被更新
题目没有说是连通图啊，也没有说从哪个点到哪个点中间有负环，只是问图中是否有负环。
1不一定能到所有节点，如果一开始从1处出发都是正权边，那所有边都无法更新，所以整个过程只有1入队再出队，根本不会往下走
哪个萌新看得懂？
妙啊
orz
太妙了
为什么 Segmentation Fault 了呢？求大佬解释
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 2010, M = 10010;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int q[N],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;
idx++;
}
bool spfa(){
int hh=0,tt=-1;
//初始状态（起点）放到队列中
for(int i=1;i<=n;i){
q[tt]=i;
st[i]=true;
}
while(tt>=hh){
int t=q[hh];//拿队头赋给t并弹出
st[t]=false;//t已经不在队列所以要标记false
//拓展t的邻接点
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
int wE=w[i];
if(dist[j]>dist[t]+wE){//如果邻接点存在更短路
dist[j]=dist[t]+wE;//则进行更新
cnt[j]=cnt[t]+1;
if(cnt[j]>=n) return true;
if(!st[j]){//如果j也不在队列中
q[tt]=j;//则入队
st[j]=true;//标记入队
}
}
}
}
return false;
}
int main()
{
scanf(“%d%d”, &n, &m);
memset(h, -1, sizeof h);
while (m – )
{
int a, b, c;
scanf(“%d%d%d”, &a, &b, &c);
add(a, b, c);
}
if (spfa()) puts(“Yes”);
else puts(“No”);
return 0;
}
多谢了
写的妙啊
if(cnt[j] >= n) return true; 为什么这一步就一定能判定，这是最短路径的时候呢
如何把spfa判最短路和负环搞在一起
没规定最短路边数的话有负环会死循环，感觉不是很好搞在一起