一、上期回顾掌握堆优化 Dijkstra 算法解决非负权单源最短路径。但 Dijkstra 遇到负权边会失效今天学习SPFA队列优化 Bellman-Ford专门处理带负权图还能判断负环。二、SPFA 基础介绍1. 适用场景求带负权边图的单源最短路径检测图中是否存在负环负权回路有负环时最短路径无意义可以无限绕环减小距离2. 核心思想基于 Bellman-Ford 原理用队列优化不断将被松弛成功的节点入队重复更新邻居节点距离每个节点重复入队次数超标 → 判定存在负环3. 限制不能处理负权回路上的最短路径只能检测负环。三、前置准备沿用邻接表存图定义数组含义const int N 10005; vectorpairint, int edge[N]; // edge[u] {v, 边权w} int dist[N]; // 起点到各点最短距离 int cnt[N]; // 记录每个节点入队次数用于判负环 bool inQueue[N];// 标记节点是否在队列中避免重复入队四、SPFA 标准模板求最短路 判负环#include iostream #include vector #include queue #include climits using namespace std; const int N 10005; const int INF INT_MAX; vectorpairint, int edge[N]; int dist[N]; int cnt[N]; bool inQueue[N]; int n, m; // 返回值true 存在负环false 无负环 bool spfa(int start) { // 初始化 fill(dist, dist N, INF); fill(cnt, cnt N, 0); fill(inQueue, inQueue N, false); queueint q; dist[start] 0; q.push(start); inQueue[start] true; cnt[start] 1; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; // 遍历所有邻边 for (auto e : edge[u]) { int v e.first; int w e.second; // 松弛操作找到更短路径 if (dist[u] ! INF dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; cnt[v]; // 关键点入队次数 节点数存在负环 if (cnt[v] n) return true; } } } } return false; } int main() { cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; edge[u].emplace_back(v, w); // 无向图额外加edge[v].emplace_back(u, w); } bool hasLoop spfa(1); if (hasLoop) { cout 图中存在负环 endl; } else { cout 最短路径 endl; for (int i 1; i n; i) { if (dist[i] INF) cout 不可达 ; else cout dist[i] ; } } return 0; }五、核心逻辑拆解1. 松弛操作if (dist[v] dist[u] w) dist[v] dist[u] w;从 u 走到 v 能得到更短距离就更新。2. 队列去重inQueue[]标记节点是否在队列同一节点不重复入队提升效率。3. 负环判定原理一个正常图每个节点最多被松弛n-1次n 为总顶点数。如果某个节点入队次数 ≥ n说明陷入负环可以无限更新距离。六、SPFA 与 Dijkstra 对比表格算法适用条件数据结构特点Dijkstra边权非负优先队列 (堆)效率高O (E logV)SPFA允许负权边不能有负环求最短路普通队列可判负环不稳定七、常见易错点距离数组初始化为无穷大起点距离置 0一定要判断dist[u] ! INF避免不可达节点更新负环判定条件cnt[v] n无向图需要双向建边八、今日核心总结SPFA 是队列优化版 Bellman-Ford支持负权边核心流程松弛 → 入队 → 循环遍历利用入队次数检测负环是考试高频考点负环存在时不存在合法最短路径负权图选 SPFA非负权图优先 Dijkstra九、课后练习搭建带负权边的图运行 SPFA 输出最短路手动构造负环验证负环检测功能对比 Dijkstra 和 SPFA 的使用场景差异
SPFA算法：负权图最短路径与负环检测
一、上期回顾掌握堆优化 Dijkstra 算法解决非负权单源最短路径。但 Dijkstra 遇到负权边会失效今天学习SPFA队列优化 Bellman-Ford专门处理带负权图还能判断负环。二、SPFA 基础介绍1. 适用场景求带负权边图的单源最短路径检测图中是否存在负环负权回路有负环时最短路径无意义可以无限绕环减小距离2. 核心思想基于 Bellman-Ford 原理用队列优化不断将被松弛成功的节点入队重复更新邻居节点距离每个节点重复入队次数超标 → 判定存在负环3. 限制不能处理负权回路上的最短路径只能检测负环。三、前置准备沿用邻接表存图定义数组含义const int N 10005; vectorpairint, int edge[N]; // edge[u] {v, 边权w} int dist[N]; // 起点到各点最短距离 int cnt[N]; // 记录每个节点入队次数用于判负环 bool inQueue[N];// 标记节点是否在队列中避免重复入队四、SPFA 标准模板求最短路 判负环#include iostream #include vector #include queue #include climits using namespace std; const int N 10005; const int INF INT_MAX; vectorpairint, int edge[N]; int dist[N]; int cnt[N]; bool inQueue[N]; int n, m; // 返回值true 存在负环false 无负环 bool spfa(int start) { // 初始化 fill(dist, dist N, INF); fill(cnt, cnt N, 0); fill(inQueue, inQueue N, false); queueint q; dist[start] 0; q.push(start); inQueue[start] true; cnt[start] 1; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; // 遍历所有邻边 for (auto e : edge[u]) { int v e.first; int w e.second; // 松弛操作找到更短路径 if (dist[u] ! INF dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; cnt[v]; // 关键点入队次数 节点数存在负环 if (cnt[v] n) return true; } } } } return false; } int main() { cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; edge[u].emplace_back(v, w); // 无向图额外加edge[v].emplace_back(u, w); } bool hasLoop spfa(1); if (hasLoop) { cout 图中存在负环 endl; } else { cout 最短路径 endl; for (int i 1; i n; i) { if (dist[i] INF) cout 不可达 ; else cout dist[i] ; } } return 0; }五、核心逻辑拆解1. 松弛操作if (dist[v] dist[u] w) dist[v] dist[u] w;从 u 走到 v 能得到更短距离就更新。2. 队列去重inQueue[]标记节点是否在队列同一节点不重复入队提升效率。3. 负环判定原理一个正常图每个节点最多被松弛n-1次n 为总顶点数。如果某个节点入队次数 ≥ n说明陷入负环可以无限更新距离。六、SPFA 与 Dijkstra 对比表格算法适用条件数据结构特点Dijkstra边权非负优先队列 (堆)效率高O (E logV)SPFA允许负权边不能有负环求最短路普通队列可判负环不稳定七、常见易错点距离数组初始化为无穷大起点距离置 0一定要判断dist[u] ! INF避免不可达节点更新负环判定条件cnt[v] n无向图需要双向建边八、今日核心总结SPFA 是队列优化版 Bellman-Ford支持负权边核心流程松弛 → 入队 → 循环遍历利用入队次数检测负环是考试高频考点负环存在时不存在合法最短路径负权图选 SPFA非负权图优先 Dijkstra九、课后练习搭建带负权边的图运行 SPFA 输出最短路手动构造负环验证负环检测功能对比 Dijkstra 和 SPFA 的使用场景差异
