下面是从零开始的图论讲解之 Bellman-Ford 与 SPFA 算法详解，适合初学者、蓝桥杯备赛者及需要理解负权图最短路径原理的读者。
🚦 Bellman-Ford 算法与 SPFA 算法求解最短路径问题 ——从零开始的图论讲解
📚 目录
- 图论基础与最短路径问题概述
- Bellman-Ford 算法详解
- 适用范围
- 核心思想
- 模板代码
- 时间复杂度
- SPFA 算法详解
- SPFA 与 Bellman-Ford 的关系
- 算法优化原理
- 模板代码
- 是否存在负环检测
- 算法对比分析
- 蓝桥杯典型真题应用
- 实战练习推荐
- 小结与学习建议
1. 📌 图论基础与最短路径问题概述
最短路径问题是图论中最常见的一类问题，目标是在图中寻找从起点到其他顶点的最短路径。
分类：
- 正权图：Dijkstra（不能处理负权边）
- 有负权图（无负环）：Bellman-Ford / SPFA
- 有负权环：可检测
2. 📘 Bellman-Ford 算法详解
✅ 适用范围
- 图中有 负权边
- 需要检测负环
- 适用于稀疏图（边数远小于点的平方）
🎯 核心思想
不断松弛所有边，最多执行 n−1 次。
如果第 n 次还有边能被松弛，说明存在 负权环。
🧠 算法流程
- 初始化所有点距离为 ∞，起点为 0；
- 重复 n−1 次遍历所有边；
- 若存在 dist[v]>dist[u]+w，就更新；
- 第 n 次再跑一次用于检测负环。
💡 模板代码（C++）
bool bellman_ford(int start, int n, vector<Edge>& edges, vector<int>& dist) {
dist.assign(n + 1, INF);
dist[start] = 0;
for (int i = 1; i < n; ++i) {
for (auto& e : edges) {
if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w)
dist[e.v] = dist[e.u] + e.w;
}
}
// 第n次判断是否存在负环
for (auto& e : edges) {
if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w)
return false; // 存在负环
}
return true;
}
⏱️ 时间复杂度
- 最坏：O(n⋅m)，其中 n 为点数，m 为边数。
3. ⚡ SPFA 算法详解（队列优化版 Bellman-Ford）
🧩 SPFA 是什么？
SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的队列优化版本，通过减少不必要的松弛操作提高效率。
🧠 算法核心优化
- 使用队列仅处理可能会更新他人最短路径的点
- 每个点在被更新时进队，避免无效操作
- 可配合计数器实现 负环检测
🧩 伪代码流程
- 起点进队，初始化距离为 0；
- 队列中不断弹出节点 u，遍历 u 的所有出边；
- 若能松弛，则更新距离，v 入队（若尚未在队中）；
- 每个点入队次数若 > n，则存在负环。
🧑💻 模板代码（C++）
bool spfa(int start, int n, vector<vector<Edge>>& graph, vector<int>& dist) {
vector<bool> in_queue(n + 1, false);
vector<int> count(n + 1, 0);
queue<int> q;
dist.assign(n + 1, INF);
dist[start] = 0;
q.push(start);
in_queue[start] = true;
count[start]++;
while (!q.empty()) {
int u = q.front(); q.pop();
in_queue[u] = false;
for (auto& e : graph[u]) {
if (dist[e.v] > dist[u] + e.w) {
dist[e.v] = dist[u] + e.w;
if (!in_queue[e.v]) {
q.push(e.v);
in_queue[e.v] = true;
count[e.v]++;
if (count[e.v] > n) return false; // 负环
}
}
}
}
return true;
}
⏱️ 时间复杂度
- 平均复杂度接近线性：O(km)，k为一个常数；
- 最坏情况仍为 O(nm)
4. 🔍 Bellman-Ford 与 SPFA 对比
| 特性 | Bellman-Ford | SPFA |
|---|---|---|
| 适用图类型 | 有负权图 | 有负权图 |
| 检测负环 | 支持 | 支持 |
| 时间复杂度 | O(n·m) | 平均 O(m)，最坏 O(n·m) |
| 是否使用队列 | 否 | 是（入队优化） |
| 稳定性 | 稳定 | 不稳定（依赖数据） |
| 编码难度 | 简单 | 中等 |
5. 🧩 蓝桥杯典型题目应用
🎯 蓝桥杯 C++ B组真题：《虫洞》
- 题意：存在双向和单向路径，单向路径可能为负，判断是否存在负权环。
- 算法建议：使用 SPFA + 入队计数检测负环。
📎 洛谷 P3865 SPFA 模板题
📎 AcWing 851. spfa求最短路
6. 🔨 实战练习推荐
7. 📌 小结与学习建议
- Bellman-Ford 是图论中基础必会的负权图算法，适合入门。
- SPFA 更高效，建议熟悉其优化思路（入队标记、入队次数等）。
- 两者都能处理负权边、检测负环，是 Dijkstra 的强力补充。
- 建议多做负环检测题 + 手写一遍模板加深理解。
发表回复