1. 先搞清楚SPFA到底解决什么问题如果你刷过图论的题或者在做路径规划、网络分析、状态转移这类开发需求大概率绕不开单源最短路径问题。SPFAShortest Path Faster Algorithm就是解决单源最短路径的一把通用快刀它支持图中存在负权边这一点比只能处理非负边的经典堆优化算法更宽松在随机图上的平均表现又比朴素的Bellman-Ford好得多。简单说SPFA用“队列松弛”的思路把Bellman-Ford那种每轮全量扫描所有边的笨办法改成只扫描“可能引起更新的点的出边”大多数情况下能把复杂度从O(VE)降到接近O(E)。这篇教程围绕SPFA给出三种最常用的图存储方式下的完整实现邻接矩阵、邻接表、链式前向星。不管你是准备算法竞赛、考研、面试还是工作中临时要做图计算都能在这里找到能直接抄的代码模板以及注释背后那些“为什么这么写”的关键细节。1.1 单源最短路径从一个点出发的最短路问题单源最短路径的定义很简单给定一张带权有向图G(V, E)再给定一个起点s求s到其他所有顶点的最短路径长度。这里的“长度”指路径上所有边权之和。典型应用包括地图导航、网络路由、任务依赖关键路径分析、游戏寻路等等。这里有一个关键认知如果图中所有边权都是非负的优先用堆优化的Dijkstra因为它稳定且快但如果图中存在负权边Dijkstra的贪心策略会失效因为你无法保证当前弹出的“最小距离点”以后不会被一条负权边进一步更新。而SPFA正好是为这种场景设计的。它不需要边权非负的假设同时还能顺手检测出图中是否存在负权环。这个能力在工程里非常有用因为数据一旦带有负权回路所有最短路径结果都失去意义。再深入一点看负权图里“已经确定了最短路”这个状态必须格外小心。一条多绕一点的路径完全可能因为中间有一条很负的边而比直达路径更短。这也是SPFA不能像Dijkstra那样“每个点出队一次就完事”的原因——它允许一个顶点反复入队、反复被重新松弛直到真的没有更短路径可找为止。1.2 为什么选SPFA而不是其他算法算法适用边权平均复杂度最坏复杂度能否检测负权环堆优化的Dijkstra非负O((VE)logV)O((VE)logV)不能Bellman-Ford任意O(VE)O(VE)能SPFA任意接近O(E)O(VE)能在“存在负权边但无负环”的图上SPFA通常是最实用的选择。首先它实现简单只有队列加松弛代码量比Bellman-Ford多不了几行其次队列操作在大多数数据上常数很小第三它不需要专门维护每一轮所有边集合的状态天然就是按需扫描。相比之下Bellman-Ford每轮都要把所有边过一遍哪怕一条边两头都没有被更新过这种全量扫描在稀疏图上浪费非常明显。但这里必须说句公道话SPFA的最坏复杂度确实是O(VE)在特定构造下甚至会退化到比普通Bellman-Ford更差的常数水平。如果题目明确告诉你图上点很多、边也很多并且数据可能故意构造来卡SPFA那对负权图更稳妥的方案是老老实实Bellman-Ford或者用Johnson算法先做重标定再跑Dijkstra。什么时候敢用SPFA什么时候该换算法我在第4节“避坑”部分会专门展开。1.3 SPFA的核心思想队列与松弛SPFA的一切都建立在一个叫“松弛”的操作上。对于一条边(u, v, w)如果发现dist[v] dist[u] w就把dist[v]更新成dist[u] w这就是一次松弛。Bellman-Ford每轮对所有边做一次松弛一轮下来至少能确定一个顶点的最短路无负环时所以需要做n-1轮复杂度自然就是O(VE)。SPFA的洞察在于只有当一个顶点u的dist在本次更新中被改小了u的出边才可能让其他点的dist也改小如果u的dist根本没变重复扫描它的出边是在浪费算力。于是算法用一个队列维护“dist刚被更新过、还没处理完”的顶点。流程是出队一个u遍历u的所有出边做松弛一旦某个v被成功更新并且v当前不在队列里就把v放入队尾。这个“谁变化了才处理谁”的思路本质上是按需松弛、动态推进所以平均下来比Bellman-Ford快非常多。为什么入队次数可以用来检测负权环这是初学者最容易困惑的地方。道理其实很朴素在没有负环的图上每个顶点一旦入队就说明找到了一条到它更短的路径。而从起点到任意一个顶点真正的最短路径不会经过同一个顶点两次否则就构成了一个环如果环权值为正绕圈只会增加总代价不可能是最短路如果环权值为负那最短路径根本不存在可以无限绕圈刷低距离。所以在无负环的图中每个顶点最多被更新入队n-1次就会收敛。一旦某个顶点入队次数超过n就可以断定图中存在负权环直接终止算法避免死循环。2. 图怎么存三种存储方案的原理与模板图论题第一步永远不是写算法而是把图存好。存储方案不仅影响代码篇幅还直接决定能不能跑过大数据用例。同一道题数据范围n100和n100000能用同一套存储吗大概率不行。下面把三种存储结构分别讲透每种都给出能直接背的模板再说清楚各适合什么场景。2.1 邻接矩阵最直观但空间开销大邻接矩阵的思路就是开一个二维数组graph[n][n]graph[i][j]存从i到j的边权不连通就存INF。判断顶点u和v之间是否有边只需要看graph[u][v]是否等于INF时间复杂度O(1)。优点是写起来极度简单调试时直接打印二维数组就能把整张图看明白。它最适合顶点数量小、边非常稠密的图一般n在1000以内还能接受超过2000内存就开始吃紧。比如n5000时5000乘5000的int数组是1亿个int约400MB很多在线评测系统直接爆内存。缺点是空间和遍历都很奢侈。即使一个顶点只有两条出边遍历它的全部出边也要从头扫到尾把整行过一遍复杂度是O(n)。再加上无法简单区分重边和自环在工程里我一般只在小规模演示或者“先把算法跑通再说”的阶段使用邻接矩阵真正上生产代码很少这么存。const int MAXN 1005; const int INF 0x3f3f3f3f; int graph[MAXN][MAXN]; int n, m;2.2 邻接表工程开发用得最多的方案邻接表的核心是每个顶点挂一条“出边链表”。在C里最常见的就是vector数组顶点u的邻居存在vector[u]里每个元素是一个Edge结构体存to终点和w边权。遍历u的出边只需要一个for循环从头跑到尾复杂度O(degree(u))对稀疏图非常友好。使用vector还有一个隐形好处重边和自环天然全部保留。你说我有两条从1到2的边一条权3一条权5SPFA在遍历时先松到3过一会儿再遇到权5那条发现dist[2]不满足更新条件自然跳过不影响正确性。相比之下邻接矩阵存重边会直接覆盖只保留最后一次写入的权值这就要手动维护最小值很麻烦。缺点也有一些。极端情况下vector扩容会带来额外拷贝开销遍历时的指针跳转对缓存不友好还有如果要频繁删除边vector的处理比较笨重。不过在绝大多数SPFA场景里邻接表是“工程上最省心”的默认选择。struct Edge { int to, w; }; vectorEdge adj[MAXN];2.3 链式前向星竞赛和高性能场景的最优解链式前向星是竞赛圈最爱用的存储结构之一本质是用数组模拟链表把“起点相同的边”串在一起。head[u]存顶点u的第一条边在edges数组中的下标Edge结构体里除了to和w还有一个next存下一条起点相同边的下标。因为没有真正的指针所以叫“前向星”——用连续数组序号模拟“指向前方兄弟”。加边用头插法新边永远插到链表头部写法非常固定const int MAXN 10005; const int MAXM 200005; struct Edge { int to, w, next; } edges[MAXM]; int head[MAXN], tot; void addEdge(int u, int v, int w) { edges[tot] {v, w, head[u]}; head[u] tot; }初始化时把所有head置为-1表示链表为空。遍历u的所有出边则是这样for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to, w edges[e].w; // 处理边(u, v, w) }为什么要用这个结构而不是vector两个原因。第一内存连续整条“邻接表”全部落在同一块数组上遍历时的缓存命中率比vector 更好性能稳定。第二初始化极快memset(head, -1, sizeof(head))一行搞定而且不存在动态扩容。缺点就是理解和写起来绕一点尤其是无向图要记得加边两次否则边数减半遍历直接出错。2.4 三种存储方式怎么选一张表说清楚存储方式空间复杂度遍历u的出边加边操作适合场景邻接矩阵O(V^2)O(V)O(1)顶点少、边密集n≤1000邻接表O(VE)O(degree)O(1)常规题目、工程开发最通用链式前向星O(VE)O(degree)O(1)大数据、竞赛、需要稳定性能我的建议是如果你写的是课后作业或者快速验证算法思路邻接矩阵最省事如果是日常开发或普通难度题目挨着vector直接用邻接表如果是正式比赛、点数和边数动辄几十万链式前向星是最能让你放心的选择。很多人纠结“学哪个”其实三种都不难真正的差距在于理解每种结构在内存和迭代上的代价。3. 手把手实现三种存储方式下的SPFA完整代码下面给三个完整可用的SPFA模板。为了对比方便三个模板保持同样的接口void spfa(int start)传入起点编号这里从0或1开始都行只要graph定义对得上最短距离结果存放在全局dist数组负权环检测统一用cnt数组。如果你平时习惯把dist直接返回改成vector 返回即可。3.1 基于邻接矩阵的实现与要点先给代码再解释几个关键点#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 1005; int graph[MAXN][MAXN]; int dist[MAXN]; int cnt[MAXN]; bool inQueue[MAXN]; void spfa_adjMatrix(int start, int n) { memset(dist, 0x3f, sizeof(dist)); memset(cnt, 0, sizeof(cnt)); memset(inQueue, false, sizeof(inQueue)); queueint q; dist[start] 0; q.push(start); inQueue[start] true; cnt[start]; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (int v 0; v n; v) { if (graph[u][v] INF) continue; if (dist[v] dist[u] graph[u][v]) { dist[v] dist[u] graph[u][v]; if (!inQueue[v]) { q.push(v); inQueue[v] true; cnt[v]; if (cnt[v] n) { // 存在负权环提前退出 return; } } } } } }这段代码里最容易被忽略的点是init。graph本身必须在外面初始化成INF不能只靠memset因为memset只能按字节填dist用0x3f3f3f3f是因为它约等于10^9两个这样的值相加不会溢出int而且memset可以一次性填好。至于为什么不用INT_MAX如果你用INT_MAX一旦dist[u] w发生整数溢出会变成负数后面的if判断全部乱套这是初学时最容易踩的坑。邻接矩阵版本的for循环很容易写成for (int v 1; v n; v)这完全没问题只要graph的下标范围对应上。但要注意矩阵的每一行都必须先填充INF否则未使用到的内存是垃圾值你的if (graph[u][v] INF)根本拦不住。3.2 基于邻接表的实现与要点#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 10005; struct Edge { int to, w; }; vectorEdge adj[MAXN]; int dist[MAXN]; int cnt[MAXN]; bool inQueue[MAXN]; void spfa_adjList(int start, int n) { memset(dist, 0x3f, sizeof(dist)); memset(cnt, 0, sizeof(cnt)); memset(inQueue, false, sizeof(inQueue)); queueint q; dist[start] 0; q.push(start); inQueue[start] true; cnt[start]; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (const Edge e : adj[u]) { int v e.to, w e.w; if (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; } } } } } }邻接表版本的循环舒服太多不需要判断“有没有这条边”因为没有边就不会出现在vector里。加边时注意无向图要加两次否则只有单向边能走通。另外SPFA里加边的顺序不会影响最终结果但会影响中间过程所以不要因为“结果一样”就忽略遍历顺序调试时顺序不同会让你以为算法写错了。还有一个容易踩的细节如果你在构造邻接表时用了push_back({v, w})那么const Edge e取引用是合理的但如果直接for (auto e : adj[u])每次循环都会复制一个Edge对象在几十万条边时白白多出拷贝开销性能会有明显下降。数据大的时候能取引用就取引用。3.3 基于链式前向星的实现与要点链式前向星配合SPFA是竞赛圈最常出现的组合因为两个都是为性能而生的写法#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 10005; const int MAXM 200005; struct Edge { int to, w, next; } edges[MAXM]; int head[MAXN], tot; int dist[MAXN]; int cnt[MAXN]; bool inQueue[MAXN]; void addEdge(int u, int v, int w) { edges[tot] {v, w, head[u]}; head[u] tot; } void spfa_chainForwardStar(int start, int n) { memset(dist, 0x3f, sizeof(dist)); memset(cnt, 0, sizeof(cnt)); memset(inQueue, false, sizeof(inQueue)); memset(head, -1, sizeof(head)); // 初始化链头 queueint q; dist[start] 0; q.push(start); inQueue[start] true; cnt[start]; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to, w edges[e].w; if (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; } } } } } }链式前向星最需要注意的就是head初始化和遍历终止条件。如果你把head初始化成0那遍历时就必须用for (int e head[u]; e ! 0; e edges[e].next)并且tot从0开始才能避免下标冲突如果你初始化成-1遍历终止条件就是e ! -1。这两个写法混用是最常见的低级错误我见过很多次一旦e为0还会访问到edges[0]它既可能是垃圾值也可能没有被初始化结果会非常诡异。另外无向图加边一定要写两次addEdge(u, v, w)和addEdge(v, u, w)。这一步漏掉图就变成有向的了跑最短路会发现有些点永远到达不了排查半天的人往往不是算法问题而是图没建对称。3.4 负权环检测入队次数的妙用三个模板里都有一个cnt[v]和if (cnt[v] n) return这就是负权环检测。要理解为什么能检测出来回到第1.3节的核心逻辑无负环时从起点到任意顶点的最短路最多经过n-1条边每个点最多被更新入队n-1次。负环一旦存在某个点会被反复松弛入队次数不停增长最终超过n这时直接return不再继续跑。这里有一个细节值得说清楚cnt[v] n中的n是指参与SPFA的顶点总数不是边的总数。边再多也不影响这个上限因为最短路路径不会重复经过同一个顶点。还有一点一旦检测到负环你的dist数组内容已经无效不要拿去输出答案应该单独用一个标志变量记录“存在负环”的状态主程序里根据标志决定是输出结果还是输出“存在负权环”。我在模板里为了简洁直接return实际项目里建议再加一个bool hasNegativeCycle。4. 复杂度、性能优化与实战避坑SPFA最迷人的地方是平均快最坑的地方也是最坏很慢。这里我不讲玄学直接说清楚复杂度是怎么来的、什么时候会被卡、怎么优化以及那些平时写代码根本不会想到的细节。4.1 时间复杂度到底怎么算平均与最坏的天壤之别平均情况下SPFA每个顶点入队次数很少一般只有一两次每条边都被扫描常数次整体接近O(E)。这也是它在随机图上比Bellman-Ford快出一个量级的原因。但在最坏情况下构造一个类似“每个点都以最小值入队每次更新都引发连锁反应”的图一个顶点可能入队n次所有边反复扫描总复杂度退化为O(VE)。对比赛选手来说这个差别不是理论问题是生死问题。有一些题目专门构建稠密负权图卡SPFA让它在OJ上超时。判断一个图“卡不卡SPFA”没有绝对标准但有几个信号可以参考点数和边数都很大、图中存在大量负权边、边权分布极端、数据是层层递进的链状结构。如果你发现数据规模超过1e5且负权很多我建议直接用Bellman-Ford的优化版本或者换Johnson算法而不是赌SPFA不被卡。4.2 SLF和LLL优化把SPFA从危重病房里救回来这里介绍两种经典优化它们能大幅改善SPFA在最坏情况下的表现。SLFSmall Label First优化入队时比较新点v的dist和队首点的dist如果dist[v]更小就插入队首否则插入队尾。这会让更小的距离点优先被处理减少大距离点反复触发更新。实现上用deque替换queuedequeint dq; if (!dq.empty() dist[v] dist[dq.front()]) { dq.push_front(v); } else { dq.push_back(v); }LLLLarge Label Last优化每次取队首前计算当前队列中所有元素的平均dist如果队首的dist大于平均值就把这个点移到队尾直到找到dist小于平均值的点再处理。它保证算法优先处理“最有希望更新别人”的点。实际编码里需要额外维护队列所有dist之和sum与元素个数len每入队一个元素就更新sum出队也一样更新。实现起来比SLF复杂一点但效果在链状构造图上很明显。个人经验是SLF代码量小、收益稳定先加SLF就够了LLL适合在SLF基础上继续压榨性能。不过两种优化都没有改变最坏复杂度只能让最坏情况的常数变小遇到真正卡SPFA的构造该换算法还是得换算法。4.3 初始化与数据范围两个不起眼但致命的细节最经典的坑是INF选择。我用的是0x3f3f3f3f因为memset(dist, 0x3f, sizeof(dist))可以直接把所有int填成这个值省去两层循环初始化。而且0x3f3f3f3f约等于1e9两个相加不会超过INT_MAX不会溢出成负数。如果你用INT_MAXdist[u] w一旦溢出变成负数后面所有判断瞬间全错而且这个错误极其隐蔽样例测试大概率还测不出来。第二个坑是数据范围。SPFA代码里MAXN和MAXM开多大直接决定你会不会越界。链式前向星的edges数组要按最大的有向边数开无向图就是2倍边数。遇到多次测试用例时head数组要用for循环或者memset重新置-1tot也要清零。我踩过一次tot忘记清零第二次建图时所有新边都接到旧边后面遍历莫名进入一个早该走完的链查了一下午。第三个容易忽略的坑是无向图加边要加倍。如果你用邻接矩阵存无向图要记得graph[u][v] graph[v][u] w如果只赋一边最短路少了一条方向结果必然不对。很多新手把“图”和“有向图”混为一谈默认双向都能走结果WA得莫名其妙。5. 常见问题与排查技巧实录下面这些是我在实际写SPFA时踩过、也在社区里见过别人反复踩的问题整理成速查形式碰到类似现象可以直接对照。5.1 现象程序死循环队列永远不为空死循环几乎都能归结到负权环检测没有生效。先检查你是不是在每次入队时都做了cnt[v]并且判断if (cnt[v] n) return。如果只在出队时统计或者把判断条件写成了cnt[v] n在恰好n次时才退出可能就会慢一步。还有一个隐蔽情况如果你用了邻接矩阵并且graph对角线graph[i][i]没有初始化成INF而是垃圾值0那么每个点会有一条指向自己的0权边松弛操作永远不会改变dist不会造成死循环但如果是负值就相当于自己有个负自环会无限入队。排查方法很简单起一个定时器或者在自己的环境里打断点看队列里的元素是否出现了重复。5.2 现象结果不对比标准答案大很多结果偏大几乎都是初始化和更新逻辑问题。第一dist数组没有全部初始化成INF起始点dist[start]也没设成0那所有更新都失效。第二inQueue数组没有清空上次测试残留的true会导致新测试用例中某些点该入队却不入队松弛断链。第三是INF选择错误使用INT_MAX导致溢出变成负数dist会被更新成莫名其妙的负值。建议每次跑新用例之前把dist、cnt、inQueue、head链式前向星全部重新初始化。5.3 现象重边太多导致更新异常重边本身不会让SPFA出错只是在邻接矩阵下会互相覆盖。例如先用graph[1][2]5后又写入graph[1][2]3前面的边直接消失。如果题目要求保留多条边中的最短路径那么只保留最小边权是对的但如果题目还涉及计数、按路径排序等需求建议用邻接表或链式前向星它们天然保留所有重边。自环则要小心负自环它会导致负权环检测触发非负自环没有影响因为松弛条件不满足点不会重新入队。5.4 排查利器对拍验证自己的SPFA是否正确如果你不确定SPFA写的对不对别反复肉眼看代码写一个对拍程序最省力。先写一个简单可靠的Bellman-Ford作为“标准答案”再随机生成小规模的图点数不超过8边随机边权范围从-5到10把两个程序的结果逐点对比。随机生成几百组数据后如果有差异立刻就能锁定期望路径在哪里断掉。用无负环数据验证完正确性再单独构造一个包含负环的数据比如三个点两两带负边确认SPFA能检测出负环。这两步做完基本可以放心把模板拿出去用。我自己平时写SPFA还有一个习惯就是在模板里特意保留cnt和inQueue数组的清晰命名不为了省变量把两者合并。排查问题的时候能直接查看队列状态和每个点的入队次数远比什么都压在一行代码里好调试。数据结构和算法这种基础工具慢一点没关系关键是稳定、能跑对、出问题能快速定位在哪里。