给定一张有向图 ( 无向图的每条边可以看作两条方向相反的有向边,从而按照有向图处理 ），每条边都有一个权值（长度）。若一条边的权值是负数，则称它是负权边。若图中存在一个环，环上各边的权值之和是负数，则称这个环为 “ 负环 ” 。
多种求解单源最短路径问题的算法。这里回顾它们的适用条件：
| 算法名称 | 能否处理负权边 | 时间复杂度 |
|---|---|---|
| Dijstra 算法 | 不能，负权可能导致当前最小的 $dist[x]$ 以后不一定最小 | $O(n^2)$ |
| 堆优化 Dijkstra 算法 | 不能，该算法仅当每个点第一次从堆中取出时执行，等价于选最小的 $dist[x]$ | $O(mlogn)$ |
| Bellman-Ford 算法 | 能，无负环时，最短路包含的边数 $<n$ ,$n-1$ 轮迭代后一定收敛 | $O(nm)$ |
| SPFA | 能，本质就是队列优化的 Bellman-Ford, 负环只是会增加出入队的速度 | $O(km)$~$O(nm)$ |
如果图中存在负环，那么直观表现为：无论经过多少轮迭代，总存在有向边 $(x,y,z)$，使得 $dist[y] > dist[x] + z$ ，Bellman-Ford 与 SPFA 算法永远不能结束。
根据抽屉原理，若存在一个 $dist[x]$，从起点 $1$ 到节点 $x$ 的最短路包含 $≥n$ 条边，则这条路径必然重复经过了某个节点 $p$ ， 换言之，这条最短路径上存在一个环，环上各点都能更新下一个点的 $dist$ 值。$p$ 绕这个环一圈，最终能更新它自己。因此，这个环的总长度是负数。每绕一圈，最短路长度只会越来越小，不可能收敛到每条边都满足三角不等式。基于这个理论有以下判定法则：
Bellman-Ford 算法判断负环
若经过 $n$ 轮迭代，算法仍未结束（仍有能力产生更新的边），则图中存在负环。
若 $n - 1$ 轮迭代之内，算法结束（所有边满足三角不等式），则图中无环。
SPFA 判定负环
- 设 $cnt[N]$ 表示从 $1$ 到 $x$ 的最短路径包含的边数， $cnt[1]=0$ 。 当执行更新 $dist[y] = dist[x] + z$ 时，同样更新 $cnt[y] = cnt[x] + 1$ 。若发现 $cnt[y]≥n$ ，则图中有负环。若算法正常结束，则图中没有负环。
- 统计每个点入队的次数，如果某个点入队 $n$ 次，则存在负环。
在处理负环时， SPFA 一般是效率比较低的，时间复杂度在 $O(nm)$左右，此时一般都会超时，经验之谈：可以在 当所有点的入队次数超过 $2n$ 时，我们认为图中有很大可能存在负环。
使用 SPFA 判负环时的两个点：
- 所有节点在初始化全部入队
- $dist[N]$ 数组可以初始化为 $0$。
假想一个虚拟源点，向图中每个点连一条边权值为 $0$ 的边，原图中存在负环等价于加上虚拟源点后也存在负环，在新图中，负环一定是可以从 虚拟源点 走到的。在新图中一开始将 虚拟源点 插入队列，并且由于虚拟源点和所有点都是相连的，所以接下来会将 其他所有点加入队列中。那么在新图上的第一次迭代之后就等价于在原图上第一次就将所有点都加到队列中。
$dist[N]$ 一开始可以被初始化 $0$ 的原因是 如果图中存在负环，那么无论是 $0$ 还是 0x3f3f3f3f ,都会被这个负环最后减成 负无穷。并且次数是无限次，那么更新也就会超过 $n$ 次，也就会达到求负环的目的。所以不管初值是多大的有限值，在经过无限次的负环后都会变成负无穷。