SPFA算法

在图论的世界里，“最短路径” 是个高频需求 —— 比如从家到公司的最优路线、网络中数据传输的最短延迟。我们知道 Dijkstra 算法很经典，但它怕负权边；Bellman-Ford 算法能处理负权边，却慢得让人着急。今天要讲的 SPFA 算法，就是两者的 “完美折中”：既能搞定负权边，效率又高，还能顺便检测讨厌的负权回路。

一、先搞懂：我们要解决什么问题？

假设有这样一张图（5 个顶点 0-4），边的权重有正有负：

• 0→1（权重 2）、0→2（权重 4）
• 1→2（权重 - 1，负权边）、1→3（权重 7）
• 2→4（权重 3）、3→4（权重 1）

我们的目标是：从顶点 0 出发，找到它到其他所有顶点的最短距离；同时判断图里有没有 “负权回路”（就是绕一圈下来总权重为负的环，比如 A→B→A 权重和为 - 2，绕得越多距离越短，根本没有最优解）。

这时候 Dijkstra 算法会 “罢工”（负权边会让它算错），Bellman-Ford 又太慢，SPFA 就该登场了。

二、SPFA 的核心思路：只跟 “有用的人” 打交道

SPFA 的全称是 Shortest Path Faster Algorithm，翻译过来就是 “更快的最短路径算法”。它快在哪里？核心秘诀就是：不做无用功，只处理能帮我们缩短路径的顶点。

我们可以用一个生活例子理解：假设你要通知朋友 “最新的最短路径消息”，Bellman-Ford 的做法是：不管朋友有没有收到过，每天挨家挨户敲门通知（遍历所有边），连续通知 n-1 天（n 是顶点数），效率极低。

而 SPFA 的做法是：

1. 先告诉起点（比如顶点 0）：“你到自己的距离是 0”，把它拉进一个 “消息队列” 里。
2. 从队列里拿出顶点 0，告诉它的邻居（1 和 2）：“从 0 到你们的距离是 2 和 4，赶紧记下来”，然后把 1 和 2 也拉进队列（因为它们现在有了新消息，可能能帮到它们的邻居）。
3. 再从队列里拿出顶点 1，告诉它的邻居（2 和 3）：“从 0→1→2 的距离是 2+(-1)=1，比之前的 4 更近，快更新！从 0→1→3 的距离是 9”。顶点 2 的距离被更新了，就把它重新拉进队列；顶点 3 是第一次收到消息，也拉进队列。
4. 继续这个过程，直到队列空了 —— 此时所有人都拿到了最短距离。

这个 “消息队列” 就是 SPFA 的灵魂：它只缓存 “有新消息要传递” 的顶点，不用遍历所有边，效率自然大幅提升。

三、代码拆解：一步步看懂 SPFA 怎么工作

下面结合开头的代码，用 “人话” 拆解每个关键部分（不用怕代码，我们只看核心逻辑）。

1. 先搭好 “图” 的架子

图由 “顶点” 和 “边” 组成，我们用 “邻接表” 来存储（就像每个顶点都有一个 “通讯录”，记录它能直达的邻居和距离）：

// 定义一条边：包含终点和权重

struct Edge {

int to; // 邻居（终点）

int weight; // 距离（权重，可正可负）

Edge(int t, int w) : to(t), weight(w) {} // 初始化边

};

// 定义图：每个顶点的通讯录集合（邻接表）

typedef vector<vector<Edge>> Graph;

比如顶点 0 的通讯录就是[Edge(1,2), Edge(2,4)]，表示能直达 1（距离 2）和 2（距离 4）。

2. 核心工具：三个数组 + 一个队列

SPFA 需要四个关键 “工具”，缺一不可：

• dist[]：距离数组，记录起点到每个顶点的最短距离（初始都是 “无穷大”，表示暂时不可达）。
• in_queue[]：标记数组，记录顶点是否在队列里（避免重复入队，比如顶点 2 已经在队列里，就不用再拉进来，减少冗余）。
• in_count[]：计数数组，记录顶点进队列的次数（用来检测负权回路）。
• queue：消息队列，缓存需要传递 “最短路径消息” 的顶点。

3. 算法步骤：从队列开始，层层传递消息

cpp

运行

vector<int> spfa(const Graph& graph, int start, bool& has_negative_cycle) { int n = graph.size(); // 顶点总数 vector<int> dist(n, INT_MAX); // 初始距离都是无穷大 vector<bool> in_queue(n, false); // 标记是否在队列中 vector<int> in_count(n, 0); // 记录入队次数 queue<int> q; // 消息队列 // 初始化起点：自己到自己的距离是0，加入队列 dist[start] = 0; q.push(start); in_queue[start] = true; in_count[start] = 1; has_negative_cycle = false; // 队列不空，就继续传递消息 while (!q.empty()) { int u = q.front(); // 取出队列里的“消息传递者”u q.pop(); in_queue[u] = false; // 标记u已经出队，后续可再入队 // 遍历u的所有邻居（查看u的通讯录） for (auto& e : graph[u]) { int v = e.to; // 邻居v int w = e.weight; // u到v的距离 // 松弛操作：如果u→v的路径更短，就更新v的距离 if (dist[u] != INT_MAX && dist[v] > dist[u] + w) { dist[v] = dist[u] + w; // 更新最短距离 // 如果v不在队列里，就拉进队列，让它也传递消息 if (!in_queue[v]) { q.push(v); in_queue[v] = true; in_count[v]++; // 入队次数+1 // 检测负权回路：入队次数>=n，说明有问题！ if (in_count[v] >= n) { has_negative_cycle = true; return dist; // 直接返回，不用再算了 } } } } } return dist; }

这里有两个关键知识点，必须讲透：

（1）什么是 “松弛操作”？

“松弛” 就是 “放松限制，找到更优解”。比如之前我们知道 0→2 的距离是 4，但后来发现 0→1→2 的距离是 2+(-1)=1，比 4 更短 —— 这时候就 “松弛” 了 0→2 的距离限制，把最短距离更新为 1。

这是所有最短路径算法的核心，就像你本来以为走大路最快，后来发现有条小路更近，就赶紧调整路线。

（2）怎么检测负权回路？

正常情况下，一个顶点的最短路径最多经过 n-1 个顶点（比如 5 个顶点，最短路径最多 4 条边，不会绕圈）。所以一个顶点最多需要进队列 n-1 次（每次更新一条更短的路径）。

如果某个顶点进队列的次数 >=n（比如 5 个顶点，顶点 2 进了 5 次队列），说明它在绕圈 —— 而且是绕一次距离就变短的负权回路（比如 2→3→2，权重和为 - 2），这时候就可以确定存在负权回路，直接返回结果就行。

4. 测试一下：看看结果对不对

我们用开头的图测试，起点是 0：

cpp

运行

int main() { int vertex_num = 5; Graph graph(vertex_num); // 添加边（顶点→邻居，距离） graph[0].push_back(Edge(1, 2)); graph[0].push_back(Edge(2, 4)); graph[1].push_back(Edge(2, -1)); graph[1].push_back(Edge(3, 7)); graph[2].push_back(Edge(4, 3)); graph[3].push_back(Edge(4, 1)); int start_vertex = 0; bool has_neg_cycle = false; vector<int> shortest_dist = spfa(graph, start_vertex, has_neg_cycle); // 打印结果 printDistance(shortest_dist, start_vertex); cout << "是否存在可到达的负权回路：" << (has_neg_cycle ? "是" : "否") << endl; return 0; }

运行结果如下：

plaintext

从 0 出发的最短距离为： 到顶点 0 为0 到顶点 1 为2 到顶点 2 为1 到顶点 3 为9 到顶点 4 为4 是否存在可到达的负权回路：否

完全符合我们的预期：0→1→2→4 的距离是 2+(-1)+3=4，是到 4 的最短路径；图里没有负权回路，所以输出 “否”。

四、关键问题：为什么一定要用队列？

很多人会问：不用队列行不行？答案是：行，但会退化成效率极低的 Bellman-Ford 算法。

我们再对比一下：

• Bellman-Ford：不管顶点有没有更新，每次都遍历所有边（比如 1000 条边，就要遍历 1000 次），时间复杂度 O (n*m)，慢得离谱。
• SPFA：用队列只处理 “距离被更新的顶点” 的邻居，相当于 “精准打击”，不用做无用功。实际场景中时间复杂度接近 O (m)（m 是边数），比 Bellman-Ford 快几个量级。

队列就像一个 “高效的消息分发中心”，只让有新消息的人去传递，而不是让所有人都乱传一通 —— 这就是 SPFA 快的根本原因。

五、SPFA 的适用场景

1. 有负权边，但没有负权回路（或需要检测负权回路）的图；
2. 稀疏图（边数少的图），SPFA 的效率优势更明显；
3. 单源最短路径（从一个起点到所有顶点的最短距离）。

如果图里全是正权边，Dijkstra 算法（加优先队列）可能更快；但如果有负权边，SPFA 就是更稳妥的选择。

总结

SPFA 算法其实一点都不复杂，核心就是三句话：

1. 用队列缓存 “有新消息（距离更新）” 的顶点，只处理这些顶点的邻居，避免无用功；
2. 用 “松弛操作” 不断更新最短距离；
3. 用 “入队次数” 检测负权回路，避免无限循环。