【数据结构与算法】最小生成树-SPFA

SPFA 与 Dijkstra 区别

Dijkstra 和 SPFA 都是求最短路径的算法，但适用场景完全不同；Dijkstra 是基于贪心思想，每次选当前距离最小的点进行扩展，要求所有边权必须是非负，否则贪心策略会失效；而 SPFA 本质是 Bellman-Ford 的优化版本，通过不断“松弛”边来更新最短路，可以处理负权边，甚至可以检测负环；从复杂度上看，Dijkstra 使用优先队列时复杂度是 O((N+M)logN)，非常稳定且高效，是最常用的最短路算法，而 SPFA 虽然平均情况下表现不错，但最坏复杂度可以退化到 O(NM)，在数据被卡时会非常慢；从实现上看，Dijkstra 用优先队列维护当前最小距离点，逻辑偏贪心，而 SPFA 用普通队列反复入队更新，更像“动态传播”；从功能上看，Dijkstra 只能解决非负权最短路问题，而 SPFA 不仅能处理负权，还能通过入队次数判断负环，这是它最大的优势；简单记忆就是：无负权用 Dijkstra，稳定又快；有负权用 SPFA，但要小心被卡。

#include<iostream> #include<vector> #include<queue> #include<climits> using namespace std; int main() { int n, m; cin >> n >> m; // 邻接表（你的风格） vector<vector<pair<int, int>>> graph(n + 1); // 读入边，边权取反 for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({v, -w}); // 关键：取反 } // SPFA初始化 vector<long long> dist(n + 1, LLONG_MAX); vector<bool> inqueue(n + 1, false); vector<int> cnt(n + 1, 0); // 入队次数，用于判负环 queue<int> q; dist[1] = 0; q.push(1); inqueue[1] = true; cnt[1] = 1; bool hasNegativeCycle = false; // SPFA主循环 while (!q.empty()) { int u = q.front(); q.pop(); inqueue[u] = false; // 遍历u的所有邻居 for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i].first; int w = graph[u][i].second; // 松弛操作（注意先判断dist[u]不是无穷大） if (dist[u] != LLONG_MAX && dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (!inqueue[v]) { q.push(v); inqueue[v] = true; cnt[v]++; // 负环检测：入队超过n次 if (cnt[v] > n) { hasNegativeCycle = true; break; } } } } if (hasNegativeCycle) break; } // 输出结果 if (hasNegativeCycle) { cout << "Forever love" << endl; } else { // 需要跑两次：从1和从n // 先存下第一次的结果 long long dist1_n = dist[n]; // 第二次：从n出发 vector<long long> dist2(n + 1, LLONG_MAX); vector<bool> inqueue2(n + 1, false); vector<int> cnt2(n + 1, 0); queue<int> q2; dist2[n] = 0; q2.push(n); inqueue2[n] = true; cnt2[n] = 1; bool hasNegativeCycle2 = false; while (!q2.empty()) { int u = q2.front(); q2.pop(); inqueue2[u] = false; for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i].first; int w = graph[u][i].second; if (dist2[u] != LLONG_MAX && dist2[v] > dist2[u] + w) { dist2[v] = dist2[u] + w; if (!inqueue2[v]) { q2.push(v); inqueue2[v] = true; cnt2[v]++; if (cnt2[v] > n) { hasNegativeCycle2 = true; break; } } } } if (hasNegativeCycle2) break; } if (hasNegativeCycle2) { cout << "Forever love" << endl; } else { long long ans = LLONG_MAX; if (dist1_n != LLONG_MAX) ans = min(ans, dist1_n); if (dist2[1] != LLONG_MAX) ans = min(ans, dist2[1]); cout << ans << endl; } } return 0; }

负权最短路 + 负环判定（SPFA）一题讲透

这道题本质是一个带负权边的最短路问题，目标是从 1 到 N 求“最短距离”；但这里的“距离减少 Wi”，等价于边权是-Wi，所以图中可能出现负权边，甚至负环；一旦存在从 1 能到达、并且还能继续影响到 N 的负环，就意味着路径可以无限变小，答案就是 "Forever love"。

因此核心就是两件事：一是最短路（不能用 Dijkstra，因为有负权），二是判断负环；这也是 SPFA 的经典应用场景。

代码整体思路 先把边权取反，构建邻接表；然后用 SPFA 从 1 出发求 dist[1→*]；过程中通过 cnt 数组统计入队次数，如果某个点入队超过 n 次，说明存在负环；这是标准判负环写法。

但这里有一个关键点很多人会错：不是“图里有负环就直接输出”，而是这个负环必须“有用”；也就是必须满足：从 1 能走到这个负环，并且从这个负环还能走到 N；否则这个负环对 1→N 的路径没有影响。

跑两次 SPFA；第一次从 1 出发，得到 dist1；第二次从 N 出发（相当于反向思考），得到 dist2；如果两边都检测到负环，就认为存在影响答案的负环；否则取两种路径的最小值。

不过这里其实可以更简单总结为一句话：
只要存在“从 1 可达且能到达 N 的负环”，答案就是无穷小。

如果没有负环，那么就是普通最短路，输出 dist[1→N] 即可。

再说一下 SPFA 的本质：它其实是 Bellman-Ford 的队列优化版本；核心操作就是“松弛”：如果 dist[v] > dist[u] + w，就更新；队列的作用是只处理“可能变优的点”；而负环检测就是利用“最短路最多经过 n-1 条边”这个性质，一旦超过 n 次更新，就说明出现了无限下降。

总结一下这题模型：负权 → SPFA；要判无穷小 → 判负环；不是所有负环都算 → 必须在 1 到 N 的路径上；掌握这一点，这类题基本就稳了。