负环

1 算法背景与问题定义

在带权有向图 $G=(V, E)$ 中，若存在一个环路 $C = v_1 \to v_2 \to \cdots \to v_k \to v_1$ ，满足环上所有边的权重之和：

\sum_{e \in C} w(e) < 0

则称该环路为一个负权环（Negative Cycle），简称负环。

1.1 负环的危害与检测意义

当图中存在从起点可达的负环时，只要沿着该负环一直绕圈，路径的总长度就可以无限减小（趋于 $-\infty$ ）。这使得单源最短路径失去有限的数学定义。在实际应用中（如差分约束系统、货币套汇检测等），检测图中是否存在负环往往是解决问题的核心环节。

根据 bellman-ford 的思想：

在一个无负环的图 $G$ 上的任意两个点 $u, v$ 之间的最短路，所经过的边数至多为 $n-1$ 条。

如果算法发现从源点出发的最短路必须包含 $\geqslant n$ 条边，由抽屉原理可知路径上必然包含重复出现的顶点，从而证明图上存在负权环。

2 方法一：基于队列的 SPFA 边数计数法（BFS 版）

1. 核心原理与推论

设 $dis(u)$ 表示当前源点到点 $u$ 的最短路估计值， $cnt(u)$ 表示当前松弛路径所包含的边的数量。

松弛操作更新规则：

1:if $dis(v) > dis(u) + w(u,v)$ then

2: $dis(v) = dis(u)+w(u,v)$

3: $cnt(v) = cnt(u) + 1$

4:end if

推论1：若在松弛过程的任意时刻出现 $cnt(v) \geqslant n$ ，则说明当前从源点到达点 $v$ 的最短路至少经过了 $n$ 条边（即 $n+1$ 个顶点），图中必然存在可达的负环。

2. 全图检测技巧：超级源点与全员初始入队

如果负环所在的连通块与指定的单个源点不连通，从该源点出发就无法检测到负环。因此，为了检测全图任意位置是否存在负环：

概念上：建立一个虚拟超级源点 $S$ ，向图中每一个节点 $1 \sim n$ 引一条边权为 $0$ 的有向边；
代码实现：只需在初始化时，将所有顶点 $1 \sim n$ 的 $dis$ 初始化为 $0$ ，并将它们全员压入初始队列！

3. BFS 模板代码

// spfa 找负环（基于队列与边数计数法）
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const long long INF = (1LL << 60);

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

const int maxn = 100000 + 5;
vector<Edge> g[maxn];
long long dis[maxn];
int cnt[maxn];       // 到每个点的最短路经过的边数
bool in_queue[maxn]; // 是否在队列中

void init_graph(int n) {
    for (int i = 1; i <= n; ++i) g[i].clear();
}

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

// 返回 true 表示检测到图中存在负环，false 表示无负环
bool spfa_has_negative_cycle(int n) {
    fill(dis + 1, dis + n + 1, 0);
    fill(cnt + 1, cnt + n + 1, 0);
    fill(in_queue + 1, in_queue + n + 1, true);

    queue<int> q;
    // 关键技巧：为了检测全图可能存在的非连通分量上的负环，
    // 相当于建立虚拟超级源点连接所有点（边权0），初始时将 1..n 全员入队！
    for (int i = 1; i <= n; ++i) {
        q.push(i);
    }

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

        for (const auto& e : g[u]) {
            int v = e.to;
            if (dis[u] + e.w < dis[v]) {
                dis[v] = dis[u] + e.w;
                cnt[v] = cnt[u] + 1;
                // 若经过的边数达到或超过 n，说明存在至少 n+1 个点，必有回路且该回路为负环
                if (cnt[v] >= n) return true;

                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    return false;
}

3 方法二：DFS 版 SPFA 判定负环

除了使用队列的 BFS 方式外，还可以使用**深度优先搜索（DFS）**来判定负环。

1. 核心原理与直觉

回顾无向图/有向图找环的原理：在 DFS 遍历树中，如果遇到了一条指向当前递归调用栈中祖先节点的“回边（Back Edge）”，说明形成了一个环。

在带权图的 DFS-SPFA 中：

我们维护一个布尔数组 in_stack[u]，表示节点 $u$ 当前是否在递归调用栈中。
从当前节点 $u$ 尝试沿着能够松弛的出边 $(u, v)$ 向深层递归探索。
若沿着松弛链访问到一个已经在栈中的节点 $v$ （即 in_stack[v] == true）：
- 这意味着从 $v$ 出发经过一系列有效松弛操作，绕了一圈回来居然能把点 $v$ 自己的距离更新得更小！
- 这严格证明了该回路上所有边的权值之和必为负数，即必然存在负环！

2. 优缺点对比

优点（特定场景极快）：如果图中确实存在负环，DFS 能够顺着一条松弛链“一路扎到底”，在许多随机图或含有明显负环的图上，常常比 BFS 版更快捕获到负环并提前退出。
缺点（最坏复杂度会退化）：在没有负环的图或网格图、精心构造的卡 SPFA 毒瘤数据上，DFS-SPFA 的回溯与重复遍历会导致时间复杂度退化至指数级甚至直接 TLE（超时）。
结论：在竞技编程与工程实践中，求最短路及通用判负环请优先使用 BFS 边数计数法（方法一）；仅在明确得知存在负环且需要极快退出的特化场景下才考虑 DFS-SPFA。

3. DFS 模板代码

// DFS 版 SPFA 判定负环
#include <iostream>
#include <vector>

using namespace std;

const long long INF = (1LL << 60);

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

const int maxn = 100000 + 5;
vector<Edge> g[maxn];
long long dis[maxn];
bool in_stack[maxn]; // 记录当前搜索递归栈上的点

void init_graph(int n) {
    for (int i = 1; i <= n; ++i) g[i].clear();
}

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

// 递归函数：若在当前松弛链上再次访问到已经在递归栈中的点，则证明存在负环
bool dfs_spfa(int u) {
    in_stack[u] = true;

    for (const auto& e : g[u]) {
        int v = e.to;
        if (dis[u] + e.w < dis[v]) {
            dis[v] = dis[u] + e.w;
            // 若被松弛的目标点 v 已经在当前 DFS 递归调用链（调用栈）中，
            // 说明绕了一圈回来还能让距离变得更小，必然存在负环！
            if (in_stack[v] || dfs_spfa(v)) {
                return true;
            }
        }
    }

    in_stack[u] = false; // 回溯出栈
    return false;
}

// 检测全图是否存在负环
bool has_negative_cycle_dfs(int n) {
    fill(dis + 1, dis + n + 1, 0);
    fill(in_stack + 1, in_stack + n + 1, false);

    for (int i = 1; i <= n; ++i) {
        if (dfs_spfa(i)) return true;
    }
    return false;
}

4 方法三：点被更新（松弛）的次数

推论2：在一个无负环的图中，任何一个点的松弛次数不可能超过 $n-1$ 次。若存在某个点 $v$ 被松弛（或入队）的次数达到或超过 $n$ 次，则必有负环。

虽然记录每个点的更新次数在理论上也完全正确，但由于每个点出队和入队的实际行为受队列排队顺序影响，通常收敛速度慢于“边数计数法”（因为一条边数长达 $k$ 条边的链，直接累加计数只需 $k$ 次松弛即可达到阈值）。因此实战推荐边数法。

5 总结

判定负环的三种主流思路：

BFS 边数计数法（推荐）：全员入队，记录 $cnt[v] = cnt[u] + 1$ ，达到 $n$ 立即返回 true。逻辑严密，不易超时，是最稳健的做法。
DFS 递归栈判回边：沿松弛链深搜，命中栈中祖先即判负环。在有负环的数据中往往秒出结果，但容易被卡到指数级。
点松弛次数计数：记录松弛次数超过 $n-1$ ，效率相对边数法稍慢。

6 相关题解

暂无相关题解