求负环的常用方法：基于$spfa$
$①$ 统计每个点入队的次数，如果某个点入队$n$次，则说明存在负环
$②$ 统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于$n$，则说明存在负环。
一般用第二种，因为第一种某个点被更新$n$次，可能要在负环上转$n$遍才能更新$n$次，最坏情况下时间复杂度是$O(n^2)$。而第二种转一圈最短路边数就可能大于$n$，所以第二种一般更快。
$spfa$求负环经验上是$(nm)$

第二种方法的两个解释：

① 一开始将所有点都加入队列中

因为负环可能单独独立出来(不连通)，所以其实我们要以所有点为起点去更新最短距离，我们可以加入一个虚拟原点，所有点到虚拟原点的距离都是$0$，然后整个图一定是连通的，则一定可以找到负环。加入虚拟原点之后第一步也会将所有点更新进队列，所以等价于我们直接将所有点加入队列。

② 不用初始化$dist$数组为$INF$

因为如果存在负环，无论$dist$[ ]是什么值都是有限的，都会一直减去无限格负环的值，最后为-∞，所以无论$dist$[ ]是什么值对判断负环都没有影响。

队列问题

由于$spfa$每个点要多次入队，所以如果用普通队列的话，需要开很长的队列才能不$WA$，这里可以考虑用循环队列，也可以直接用$quque$

例题

模板题：$spfa$判断负环 虫洞