卡SPFA是算法竞赛圈里一个经久不衰的“手艺活”了。虽然SPFA在随机数据下跑得飞快但它的贪心松弛策略确实存在明显的软肋。要构造出让它跑到最坏复杂度 O(VE) 的数据核心思路就是‌诱导它反复进行无效更新‌让节点多次入队不断更新次短路就是不给它走最短路。结合大家总结的经验这里有几套经典的“卡SPFA”数据构造方案从易到难你可以试试看1. 朴素链套菊花图最经典专治各种优化这是最基础也最有效的方法专门欺骗SPFA的贪心策略。‌构造原理‌构造一条长长的链链上的边权为负或很小链上的每个节点都额外连向一个巨大的菊花图中心。算法会沿着链不断更新每更新一个链上节点就会触发对整个菊花图的重新松弛。这样菊花图会被反复更新 kk 次总复杂度轻松达到 O(n2) 级别。‌适用场景‌能有效卡掉朴素SPFA甚至对SLFSmall Label First和LLLLarge Label Last优化也有奇效。比如在链上构造几个并列的小边权边就能欺骗SLF优化让算法多次进入菊花图。2. 随机网格图正权图杀手如果题目限制必须为正权边网格图就是首选。‌构造原理‌构造一个行数远小于列数的网格图例如 10×10000。关键技巧在于将纵向边的权值设得非常小比如0或1而横向边和斜边的权值设得很大且随机。这样从起点到某个点会存在很多条长度相近但边数不同的路径。SPFA的BFS特性会让它先探索那些边数少但权值可能并非最优的路径导致节点被重复入队和更新。‌适用场景‌正权图能有效卡掉朴素SPFA和许多优化变种。3. 进阶组合与对抗优化随着大家对SPFA的理解加深各种优化如SLF带容错、mcfx优化也被提出但同样有办法破解。‌对抗SLF带容错‌这种优化在边权之和较小时表现不错。卡它的方法就是‌把边权总和开得巨大‌最好超过 10121012这样容错机制就几乎失效了。‌对抗mcfx优化‌该优化在网格图上表现优秀但在‌菊花图‌上表现很差。所以网格套菊花这类组合图往往能通杀。‌见招拆招的通用优化出题人视角‌‌随机取点‌每次从队列取队头前先把队头与队内随机一个元素交换。这能有效克制菊花图。‌随机出边‌当前点出队时将出边暂存以随机顺序访问。这同样能打乱被精心构造的松弛顺序。总的来说SPFA之所以“死”了就是因为它这种容易被针对的复杂度上界。在非随机的一般图或构造图上它确实很容易被卡到超时。所以现在除非题目明确有负权边否则大家基本都首选稳定的Dijkstra堆优化了。不过了解这些卡法反过来也能帮我们更深刻地理解最短路算法的本质。