关于 SPFA，它真的死在“方格图”手里了吗？

SPFAShortest Path Faster Algorithm是一个让人又爱又恨的存在。它写起来比 Dijkstra 简单还能处理负权边在随机图上跑得飞快。但如果盲目套用 SPFA可能会收获一串鲜红的TLE。为什么方格图天生“克” SPFA与其说 SPFA 是一个最短路算法不如说它是一个基于队列优化的迭代松弛工具。它的核心逻辑是“只要一个点uuu的最短距离变小了那么它所有出边的终点vvv都有可能被进一步更新。”在 Dijkstra 算法中贪心策略保证了每个节点出队即为最优解distdistdist具有单调性。而 SPFA 不具备单调性。在方格图中从起点到终点存在指数级数量的简单路径。如果通过控制边序或权重使算法先沿着一条边数较多、初始权值较大的路径长链更新了后方大量节点随后才扫描到一条总权值更小的‘捷径’SPFA 将不得不对所有受影响的后继节点进行重复松弛与重新入队。出题人可以利用这一点构造多达O(V)O(V)O(V)层这种“捷径”。每发现一条新的捷径SPFA 就要把后面的节点重新洗一遍。最终每个节点入队的次数不再是常数kkk而是变成了线性O(V)O(V)O(V)导致总复杂度退化为O(V⋅E)O(V \cdot E)O(V⋅E)即O(V2)O(V^2)O(V2)方格图中E≈4VE \approx 4VE≈4V。SPFA 的效率模型W∑i1∣V∣(counti×out_degreei)W \sum_{i1}^{|V|} (count_i \times out\_degree_i)Wi1∑∣V∣​(counti​×out_degreei​)变量定义WWW算法的总工作量即松弛操作的总次数。∣V∣|V|∣V∣图中节点的总数。counticount_icounti​节点iii进入队列并被取出的总次数。out_degreeiout\_degree_iout_degreei​节点iii的出度即从该点出发的边数。总工作量W∑(counti×out_degreei)W \sum (count_i \times out\_degree_i)W∑(counti​×out_degreei​)。在方格图中out_degree≈4out\_degree \approx 4out_degree≈4counti≈Vcount_i \approx Vcounti​≈V。则W≈4×V×V4V2W \approx 4 \times V \times V 4V^2W≈4×V×V4V2。构造“捷径陷阱”for(inti0;iR-1;i){for(intj0;jC;j){intcuri*Cj;intritcur1;intdowcurC;intcrodow1;adde(cur,rit,1);adde(cur,dow,1);adde(cur,cro,10);}}代码中定义了三种边水平边 (rit)权值为 1。垂直边 (dow)权值为 1。对角边 (cro)权值为 10。从(i,j)(i, j)(i,j)到达其右下角邻居(i1,j1)(i1, j1)(i1,j1)走对角线只需要1 步代价 10而走正交边右下需要2 步代价112112112。当CN,RMCN, RMCN,RM时二维灾难的叠加在 SPFA 的 BFS 逻辑下它会按队列的先后顺序处理节点。对角线虽然代价高10但它能在第 1 轮迭代就触达(i1,j1)(i1, j1)(i1,j1)。此时SPFA 会带着这个错误的高代价10继续向右、向下扩散污染后续大量的节点。由于每一行、每一列都存在这种“先用对角线走捷径后用正交边纠正”的情况每一层级的更新都会触发下一层级的集体重洗。入队总次数会随着网格的面积呈非线性爆发。理论上每个节点可能被重新入队O(V)O(\sqrt{V})O(V​)到O(V)O(V)O(V)次。W≈O((M×N)2)W \approx O((M \times N)^2)W≈O((M×N)2)如果是一个500×500500 \times 500500×500的图节点数 25 万平方级的操作量直接奔向百亿量级必死无疑。当CN,R2CN, R2CN,R2时细长长链的“全量背刺”这种情况最为隐蔽且致命。由于只有两行图变成了一条极其细长的带状结构。当第一行第 i 个节点被纠正为更小的值时它必须触发第二行第 i1 个及之后所有节点的重新入队。当第一行第 i1 个节点被纠正时又要再触发一遍。在NNN较小时队列的处理速度尚能覆盖这种重复。当NNN足够大队列中堆积的“待修正”任务呈几何倍数增加。此时正确的信息在队尾苦苦挣扎而错误的信息已经跑到了终点。每一次微小的修正都会导致后面大量节点集体“反悔”重跑。虽然只有两行但它把 SPFA 退化成了最纯粹的O(N2)O(N^2)O(N2)。在N6000N6000N6000时600023.6×1076000^2 3.6 \times 10^7600023.6×107考虑到每个点出队还要扫描 3 条边常数因子放大后轻松突破 1 秒的限时。这段代码利用了“短路Steps代价大长路Steps代价小”的悖论。在2×N2 \times N2×N的长条图中这种矛盾被拉到了极致让 SPFA 在“不断纠错”的死循环中耗尽寿命。那些“玄学优化”有用吗为了救活 SPFA大佬们发明过很多优化手段但在精心构造的方格图面前大多是“缓刑”SLF (Small Label First)如果待入队节点的距离小于队首就插到队头。SLF 在面对诱导性极强的‘阶梯式’权值时会导致队列频繁调整反而增加常数开销。LLL (Large Label Last)只有距离小于平均值的才出队。计算平均值本身就有开销面对强针对性数据时效果有限。所以不要试图用“玄学优化”去挑战出题人卡 SPFA 的决心。总结满足“步数短的路径权值大步数长的路径权值小”SPFA 就会在网格图中反复横跳。这样节点就会频繁入队算法复杂度达到O(N2)O(N^2)O(N2)私房话“稳”要比“快那一点点”重要。方格图是容易构造出极端数据的场景之一。当你在写while(!q.empty())的时候想想有没有可能是被卡如果是请自觉右手拐弯写 Dijkstra。