一、算法概述

贝尔曼-福特算法（Bellman-Ford Algorithm）是一种求解单源最短路径的经典算法。与 Dijkstra 不同，Bellman-Ford 能够处理含负权边的图，并且可以检测图中是否存在负权环（negative cycle）。

SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的队列优化版本，通过只对距离被更新的节点进行松弛，在实践中大幅减少了无效操作，平均性能接近 $O(E)$，但在最坏情况下仍为 $O(VE)$。

二、核心思想

Bellman-Ford

核心思想是逐轮松弛：

• 在一个不含负环的图中，任意两点间的最短路径最多包含 $V-1$ 条边
• 因此，对所有边进行 $V-1$ 轮松弛操作，第 $k$ 轮之后，$dist[v]$ 表示从源点出发经过最多 $k$ 条边到达 $v$ 的最短距离
• 第 $V$ 轮如果还能松弛，则说明图中存在负权环

SPFA

核心思想是按需松弛：

• 不盲目地每一轮松弛所有边，而是维护一个队列，只对"最近距离被更新"的节点的出边进行松弛
• 只有距离变小，才可能影响其邻接节点的距离，因此只需将被更新的节点入队
• 如果某个节点入队次数超过 $V$ 次，则存在负环

三、算法步骤/伪代码

Bellman-Ford

BellmanFord(图 G, 源点 s):
    dist[1..V] = +∞
    dist[s] = 0

    for i = 1 to V-1:                 // V-1 轮松弛
        for 每条边 (u, v, w) in G:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    // 第 V 轮：检测负环
    for 每条边 (u, v, w) in G:
        if dist[u] + w < dist[v]:
            return "存在负环"

    return dist

SPFA

SPFA(图 G, 源点 s):
    dist[1..V] = +∞, dist[s] = 0
    inQueue[1..V] = false
    cnt[1..V] = 0                    // 记录入队次数（负环检测用）
    队列 q，q.push(s), inQueue[s] = true

    while q 非空:
        u = q.front(), q.pop()
        inQueue[u] = false

        for 每条出边 (u, v, w):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not inQueue[v]:
                    q.push(v)
                    inQueue[v] = true
                    cnt[v]++
                    if cnt[v] >= V:
                        return "存在负环"

    return dist

四、C++ 代码实现

以下代码同时包含 Bellman-Ford 和 SPFA 两种实现，完整可运行，并包含负环检测。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll INF = LLONG_MAX / 2; // 用较大值避免溢出，而非 LLONG_MAX

struct Edge {
    int from, to;
    ll weight;
};

// ==================== Bellman-Ford 实现 ====================
class BellmanFord {
private:
    int V;
    vector<Edge> edges; // 边列表

public:
    BellmanFord(int n) : V(n) {}

    void addEdge(int u, int v, ll w) {
        edges.push_back({u, v, w});
    }

    // 返回 {是否有负环, 最短距离数组}
    // hasNegativeCycle = true 表示存在负环，此时 dist 无意义
    pair<bool, vector<ll>> shortestPath(int src) {
        vector<ll> dist(V, INF);
        dist[src] = 0;

        // V-1 轮松弛
        for (int i = 0; i < V - 1; ++i) {
            bool updated = false;
            for (auto& e : edges) {
                if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[e.from] + e.weight;
                    updated = true;
                }
            }
            if (!updated) break; // 提前终止优化
        }

        // 第 V 轮：检测负环
        for (auto& e : edges) {
            if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
                return {true, dist}; // 发现负环
            }
        }
        return {false, dist};
    }
};

// ==================== SPFA 实现 ====================
class SPFA {
private:
    int V;
    vector<vector<pair<int, ll>>> adj; // 邻接表

public:
    SPFA(int n) : V(n), adj(n) {}

    void addEdge(int u, int v, ll w) {
        adj[u].push_back({v, w});
    }

    // 返回 {是否有负环, 最短距离数组}
    // hasNegativeCycle = true 表示存在从 src 可达的负环
    pair<bool, vector<ll>> shortestPath(int src) {
        vector<ll> dist(V, INF);
        vector<bool> inQueue(V, false);
        vector<int> cnt(V, 0);       // 入队次数
        dist[src] = 0;

        queue<int> q;
        q.push(src);
        inQueue[src] = true;
        cnt[src] = 1;

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

            for (auto& edge : adj[u]) {
                int v = edge.first;
                ll w = edge.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (!inQueue[v]) {
                        q.push(v);
                        inQueue[v] = true;
                        cnt[v]++;
                        // 入队次数 >= V 说明存在负环
                        if (cnt[v] >= V) {
                            return {true, dist};
                        }
                    }
                }
            }
        }
        return {false, dist};
    }
};

// ==================== 主函数 ====================
int main() {
    cout << "========== Bellman-Ford 演示 ==========" << endl;
    {
        BellmanFord bf(5);
        // 构造一个有负权边但无负环的图
        bf.addEdge(0, 1, 6);
        bf.addEdge(0, 2, 7);
        bf.addEdge(1, 2, 8);
        bf.addEdge(1, 3, 5);
        bf.addEdge(1, 4, -4);  // 负权边
        bf.addEdge(2, 3, -3);  // 负权边
        bf.addEdge(2, 4, 9);
        bf.addEdge(3, 1, -2);  // 负权边（但不形成负环）
        bf.addEdge(4, 3, 7);

        auto [hasNeg, dist] = bf.shortestPath(0);
        if (hasNeg) {
            cout << "检测到负环！" << endl;
        } else {
            cout << "源点 0 到各节点的最短距离:" << endl;
            for (int i = 0; i < 5; ++i) {
                cout << "0 -> " << i << " : ";
                if (dist[i] == INF) cout << "不可达" << endl;
                else cout << dist[i] << endl;
            }
        }
    }

    cout << "\n========== SPFA 负环检测演示 ==========" << endl;
    {
        SPFA spfa(4);
        // 构造一个含有负环的图：0-1-2-3-1（负环：1->2->3->1 权重：1+(-5)+1=-3<0）
        spfa.addEdge(0, 1, 5);
        spfa.addEdge(1, 2, 1);
        spfa.addEdge(2, 3, -5);   // 负权
        spfa.addEdge(3, 1, 1);    // 回到1，形成负环 1→2→3→1: 1+(-5)+1=-3

        auto [hasNeg, dist] = spfa.shortestPath(0);
        if (hasNeg) {
            cout << "检测到负环！节点1→2→3→1的总权重为负。" << endl;
        } else {
            cout << "未检测到负环" << endl;
        }
    }

    cout << "\n========== SPFA 正常最短路演示 ==========" << endl;
    {
        SPFA spfa(5);
        // 与上面 Bellman-Ford 相同的图
        spfa.addEdge(0, 1, 6);
        spfa.addEdge(0, 2, 7);
        spfa.addEdge(1, 2, 8);
        spfa.addEdge(1, 3, 5);
        spfa.addEdge(1, 4, -4);
        spfa.addEdge(2, 3, -3);
        spfa.addEdge(2, 4, 9);
        spfa.addEdge(3, 1, -2);
        spfa.addEdge(4, 3, 7);

        auto [hasNeg, dist] = spfa.shortestPath(0);
        if (hasNeg) {
            cout << "检测到负环！" << endl;
        } else {
            cout << "源点 0 到各节点的最短距离:" << endl;
            for (int i = 0; i < 5; ++i) {
                cout << "0 -> " << i << " : ";
                if (dist[i] == INF) cout << "不可达" << endl;
                else cout << dist[i] << endl;
            }
            // 预期：0→0:0, 0→1:2, 0→2:7, 0→3:4, 0→4:-2
        }
    }

    return 0;
}

五、复杂度分析

Bellman-Ford

• 时间复杂度：$\mathbf{O(VE)}$

  • $V-1$ 轮松弛，每轮遍历所有 $E$ 条边
  • 可加入提前终止优化：若某轮没有发生松弛则提前结束

• 空间复杂度：$\mathbf{O(V + E)}$

  • dist 数组：$O(V)$
  • 边列表存储：$O(E)$

SPFA

• 时间复杂度：

  • 平均：$\mathbf{O(E)}$（实践中通常很快）
  • 最坏：$\mathbf{O(VE)}$（可被刻意构造的数据卡到退化）

• 空间复杂度：$\mathbf{O(V + E)}$

  • 邻接表：$O(V + E)$
  • dist、inQueue、cnt 数组 + 队列：$O(V)$

六、应用场景

场景	说明
含负权边的最短路径	比 Dijkstra 适用范围更广
负环检测	判断图中是否存在权重和为负的环（如套汇问题）
差分约束系统	将不等式约束转化为图的最短路求解
费用流	最小费用最大流中找负环消圈
套汇检测	货币兑换中是否存在套利机会

注意事项：

• SPFA 虽然在随机数据上表现优秀，但在竞赛中可能被出题人造数据卡到最坏复杂度。对于非负权图，优先使用 Dijkstra。
• Bellman-Ford 也可以用来求最长路径（将边权取负，同时检测正环）。

七、经典例题

例题1：判断负环

题目描述：给定一个 $n$ 个节点、$m$ 条边的有向图，边权可能为负数。判断图中是否存在负权环。

可直接使用上述 SPFA 类的 shortestPath 方法，从其返回值 pair<bool, vector<ll>> 中的 bool 判断是否存在负环。代码见上文 SPFA 负环检测演示部分。

---

例题2：含负权边的最短路

题目描述：给定一个有向带权图（可能存在负权边，但保证无负环），求从 $1$ 到 $n$ 的最短距离。

以下是基于 SPFA 的模板题完整代码：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, ll>>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v; ll w;
        cin >> u >> v >> w;
        --u; --v;
        adj[u].push_back({v, w});
    }

    const ll INF = LLONG_MAX / 2;
    vector<ll> dist(n, INF);
    vector<bool> inQ(n, false);
    vector<int> cnt(n, 0);
    dist[0] = 0;

    queue<int> q;
    q.push(0);
    inQ[0] = true;
    cnt[0] = 1;

    bool hasNegCycle = false;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQ[u] = false;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            ll w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQ[v]) {
                    q.push(v);
                    inQ[v] = true;
                    if (++cnt[v] >= n) { hasNegCycle = true; break; }
                }
            }
        }
        if (hasNegCycle) break;
    }

    if (hasNegCycle) {
        cout << "存在负环" << endl;
    } else {
        cout << (dist[n - 1] == INF ? -1 : dist[n - 1]) << endl;
    }
    return 0;
}