SPFA 与 Dijkstra 区别Dijkstra 和 SPFA 都是求最短路径的算法但适用场景完全不同Dijkstra 是基于贪心思想每次选当前距离最小的点进行扩展要求所有边权必须是非负否则贪心策略会失效而 SPFA 本质是 Bellman-Ford 的优化版本通过不断“松弛”边来更新最短路可以处理负权边甚至可以检测负环从复杂度上看Dijkstra 使用优先队列时复杂度是 O((NM)logN)非常稳定且高效是最常用的最短路算法而 SPFA 虽然平均情况下表现不错但最坏复杂度可以退化到 O(NM)在数据被卡时会非常慢从实现上看Dijkstra 用优先队列维护当前最小距离点逻辑偏贪心而 SPFA 用普通队列反复入队更新更像“动态传播”从功能上看Dijkstra 只能解决非负权最短路问题而 SPFA 不仅能处理负权还能通过入队次数判断负环这是它最大的优势简单记忆就是无负权用 Dijkstra稳定又快有负权用 SPFA但要小心被卡。#includeiostream #includevector #includequeue #includeclimits using namespace std; int main() { int n, m; cin n m; // 邻接表你的风格 vectorvectorpairint, 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初始化 vectorlong long dist(n 1, LLONG_MAX); vectorbool inqueue(n 1, false); vectorint cnt(n 1, 0); // 入队次数用于判负环 queueint 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出发 vectorlong long dist2(n 1, LLONG_MAX); vectorbool inqueue2(n 1, false); vectorint cnt2(n 1, 0); queueint 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 的路径上掌握这一点这类题基本就稳了。