负环判定

负环判定的原理与实现：SPFA 与 Bellman-Ford 检测负环。

  • 负环
  • SPFA
  • Bellman-Ford
  • 最短路

一句话算法

如果一条最短路被松弛出了至少 nn 条边，那么它一定绕过了某个点，也就存在负环。

问题模型

给定一个带权有向图，判断图中是否存在一个环，使得环上边权和小于 0。

负环会让最短路没有下界：只要沿着负环多绕几圈，路径长度就能不断变小。因此许多最短路题需要先判断负环是否存在。

核心直觉

在一个没有负环的图中，从任意起点到任意终点的最短路一定可以取为简单路径。简单路径不会重复经过同一个点，所以最多经过 n−1n-1 条边。

如果某个点的距离被更新时，对应路径边数已经达到 nn，这条路径上必然重复了某个点，形成了一个环。又因为这次更新让距离变小，所以这个环的权值和是负数。

算法步骤

  1. 把所有点初始距离设为 0，并全部放入队列。这等价于建立一个超级源点，用 0 权边连向所有点，可以处理非连通图。
  2. 每次从队列取出点 u，枚举出边 u -> v。
  3. 如果 dist[v] > dist[u] + w，说明可以松弛：
    • 更新 dist[v]。
    • 令 relax_count[v] = relax_count[u] + 1，表示当前路径边数。
  4. 如果 relax_count[v] >= n，说明出现负环。
  5. 否则把 v 放回队列继续传播。

算法证明

关键不变量： 每次 dist[v] 被更新时，relax_count[v] 表示当前这条更短路径使用的边数。

  1. 无负环时： 任意最短路都可以删去重复点，变成简单路径，因此边数不超过 n−1n-1。
  2. 超过边数时： 若某次更新得到一条边数至少为 nn 的更短路径，根据抽屉原理，路径中至少有一个点重复出现。
  3. 重复点形成环： 两次出现同一点之间的部分构成一个环。
  4. 环为负： 如果这个环权值非负，删除它不会让路径变长，和“当前更新得到更短路径”矛盾。因此这个环权值必须为负。
  5. 结论： 出现 relax_count >= n 当且仅当松弛过程发现了负环。

复杂度分析

SPFA 判负环的最坏复杂度仍可能达到 O(nm)O(nm)，但实现简单，常用于竞赛模板。若题目对最坏复杂度要求严格，应考虑 Bellman-Ford、差分约束特殊结构或其他建模优化。

空间复杂度为 O(n+m)O(n+m)。

代码实现

下面模板读入 n m 和 m 条有向边 u v w，输出是否存在负环。

cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

        #include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    long long w;
};

struct NegativeCycleSPFA {
    int n;
    vector<vector<Edge>> graph;
    vector<long long> dist;
    vector<int> relax_count;
    vector<bool> in_queue;

    explicit NegativeCycleSPFA(int n)
        : n(n),
          graph(n + 1),
          dist(n + 1, 0),
          relax_count(n + 1, 0),
          in_queue(n + 1, false) {}

    void add_edge(int u, int v, long long w) {
        graph[u].push_back({v, w});
    }

    bool has_negative_cycle() {
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            q.push(i);
            in_queue[i] = true;
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            in_queue[u] = false;

            for (const auto& e : graph[u]) {
                int v = e.to;
                if (dist[v] > dist[u] + e.w) {
                    dist[v] = dist[u] + e.w;
                    relax_count[v] = relax_count[u] + 1;
                    if (relax_count[v] >= n) return true;
                    if (!in_queue[v]) {
                        q.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }

        return false;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    NegativeCycleSPFA spfa(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        spfa.add_edge(u, v, w);
    }

    cout << (spfa.has_negative_cycle() ? "Yes" : "No") << '\n';
    return 0;
}

测试用例

输入：

3 3
1 2 1
2 3 -3
3 1 1

输出：

Yes

这个环的总权值是 1 + (-3) + 1 = -1，所以存在负环。

应用分类详解

负环判定的本质是判断“约束能否被无限压低”。

一、最短路合法性检查

典型模式： 图中有负边，题目要求最短路或判断是否存在无限变小。 识别信号： 出现“负权边”“负环”“最短路不存在”。 核心建模： 用 Bellman-Ford/SPFA 松弛过程判断是否可以持续变小。

应用场景 经典题目 核心思路
负环模板 luogu-P3385 多组图判断是否存在负环
最短路前置检查 luogu-P4779 有负权时不能直接使用 Dijkstra

二、差分约束可行性

典型模式： 给出大量形如 xv≤xu+wx_v \le x_u + w 的不等式。 识别信号： 题面是变量大小关系、约束系统、是否矛盾。 核心建模： 不等式转成边 u -> v，如果出现负环则约束不可行。

应用场景 经典题目 核心思路
差分约束系统 luogu-P5960 建图后用负环判断矛盾

三、分数规划与环权优化

典型模式： 判断是否存在平均权值小于某个值的环。 识别信号： 题目问“最小平均环”“平均值是否可达”。 核心建模： 二分答案，把边权改成 w-mid，再判负环。

应用场景 经典题目 核心思路
最小平均环 luogu-P3199 二分平均值，用负环判定可行性

经典例题

  1. luogu-P3385 SPFA 判负环模板题。注意图可能不连通，所以要使用超级源点思想。

  2. luogu-P5960 差分约束模板题。约束矛盾本质上就是图中出现负环。

  3. luogu-P3199 最小平均环。把“平均值”转成边权调整后的负环判定。

参考