APSP与距离积的细粒度等价

距离积枚举一个中间点，把两段路线接起来。要将它变成最短路问题，可以让图只有“左层→中层→右层”，这样每条合法路线恰好选择一个中间点。

反向则把允许的路线长度翻倍。第一次表中只容许一条边；两张表相乘后容许两条，再平方容许四条。无负环时，总能删除重复顶点间的非负闭合段，保留至多n−1条边的最短路，所以只需对数次倍增。

这与Floyd–Warshall理路Floyd–Warshall 算法Floyd–Warshall algorithm以允许的中间顶点集合为阶段计算全部顶点对最短路。的阶段不同。Floyd依次放开“可作中间点的顶点集合”，这里依次放开“最多走多少条边”；附件用Floyd作为三层图的独立现成工具，不将两种状态定义混在一起。

三层图没有额外路线 ​

建立互不相交的顶点层L、M、R，各含n点。有限Aᵢₖ对应Lᵢ→Mₖ，权Aᵢₖ；有限Bₖⱼ对应Mₖ→Rⱼ，权Bₖⱼ。没有其他弧。

任意Lᵢ到Rⱼ的路线都恰为Lᵢ→Mₖ→Rⱼ，反之每个有限候选都对应这样一条路线。因此该点对距离正是(A★B)ᵢⱼ。即使权重为负，图仍无环，必满足APSP承诺。无候选时，两边都为+∞。

例如

得到

第二行第三列的候选为−1+1=0、2+∞、5+0=5，最小值由中间点0给出。图中对应L₁→M₀→R₂。附件确实构造9点图并运行Floyd，读取左到右的九个距离，与直接枚举27个候选核对。

倍增必须保留零成本等待 ​

先建D₀：对角含0，其他位置初为+∞，再将实际弧权取最小。令

不变量是Dᵣ[i,j]等于从i到j、至多2^r条弧的游走最小成本。有限长度上只有有限多份弧序列，因而这个最小值存在；此处暂不需要无负环。

归纳时，两个各至多2^r条弧的见证拼成至多2^(r+1)条弧，说明每个候选合法。反过来，任一不超过2^(r+1)条弧的游走，都能在第min(2^r,长度)条后切开，两段长度都不超过2^r；短段或空段由对角零成本等待容纳。因此递推既不漏路线，也不编造更短值。

取五点图，点4孤立，其余弧为0→1:4、1→2:−2、0→2:8、2→3:3、1→3:6、3→1:0；另有一条0→1:7的平行弧。则

这里1→2→3→1权和为1，不能靠绕圈降价。最短路线含三条弧，在容许四步时已出现；若没有对角等待，“恰好四步”表未必包含这条三步路线。

负环时输出什么 ​

无负环时，删掉重复顶点之间的非负闭合段不会增加成本，所以只需容许n−1步。为了同时诊断承诺失守，附件继续到K≥n的最小2幂，故K<2n（n≥1时）。

若最终D[v,v]<0，递推见证是一条真实负费用闭合游走；把闭合游走分解为简单环，至少一个环为负。反过来，任意负环包含一条至多n条弧的简单负环，其某个对角元必已为负。因此负对角元恰好检测全图负环，包括断开分量和负自环。

在上例增加3→1:−2后，1→2→3→1权和变为−1。八步表的D[1,1]=−2，附件输出两次该环的六个实际弧ID作为闭合游走证据。此时有限表项只表示受步数限制的最小值，不能冒充真正APSP距离。附件返回NEGATIVE_CYCLE，不试图把所有受影响点对写成−∞；这项扩展输出由旧Floyd页另行说明。

有限哨兵不能碰运气 ​

若用H代替无穷，H加负数可能变成小于H的值，错误地制造“可达”。例如本来缺失的一段写成H=20，接上−10后得到10，不能凭它小于20就认定存在路线。

若目标乘法器只接受有限整数，可在每次乘积前取U为两个输入中有限条目的最大绝对值，并将+∞替换为H=3U+1。真正有限候选在[−2U,2U]内；含一项哨兵的候选至少H−U=2U+1，含两项则更大。乘完后，把大于2U的结果恢复为+∞，便精确保留答案。U=0时H=1仍成立。下一轮必须重新按真实有限条目定界，不能让假哨兵一路参与后续语义。

形式陈述中的T(n,U)默认接受+∞标记。若用此适配调用只收有限整数的乘法器，实际权界扩大为3U+1；在倍增过程中可粗界为6nW+1。常数扩大不改变多项式有界权的位长结论，但必须写进具体oracle参数。

位长、输出和见证都要分别收费 ​

截至K<2n步，任何有限候选都来自至多2n条原弧，绝对值≤2nW。每轮O(n²)个条目需要O(log(nW+2))位，而不是能免费容纳任意实数。若W=n^c，位长仍为O(log n)，但常数依赖固定c；若W以任意长二进制给出，保留log W因子，不能把多项式于W的算法称作多项式于输入位长。

这里的APSP输出是距离矩阵，共n²项。显式写出全部n²条最短路径可能需要Θ(n³)条弧，不能算进一个声称次三次的输出接口。教学乘法器枚举全部k时顺带记最小下标；保留各层下标，用栈展开一对端点的见证，耗O(n)步、至多2n条原弧。所有层的这类记录占O(n²log(n+1))空间。

这些argmin记录是附件的额外教学功能。一般的快速距离积oracle可能只输出数值，不能不经证明就要求它免费返回全部路径或argmin。只保存当前、下一张数值表的倍增归约，外层工作空间为O(n²)，另加所用乘法器空间。

附件采用朴素O(n³)乘法，所以完整倍增实现为O(m+n³log(n+1))时间（n≥2）；它验证的是归约和证据，不是一个新的真次三次APSP程序。用O(n^(3−η))目标求解器替换后，对数调用与读写成本才给出某个更小η′>0的O(n^(3−η′))算法。随机求解器还需按整张矩阵正确的成功率放大，并计全部调用的失败概率。

历史假设与归约的当前含义 ​

传统整数权APSP假设主张：在经典O(log n)字宽RAM上，对足够大的固定多项式权值范围，不存在有界错误的O(n^(3−ε))精确算法；无负环是输入承诺。[2, Hypothesis3] 它并不禁止削去对数因子，也不直接涵盖实数单位成本、量子算法或近似距离。

截至2026-10-09，Alman与Vassilevska Williams在2026-10-05的预印本中报告了多项式有界整数权APSP及距离积的确定性O(n^2.9995)算法，明确指出这反驳上述传统假设。[3, Theorems2,22] 本页没有重证或独立审计该76页算法；这里证明的三层图和倍增归约不以猜想为前提，也不依赖新预印本的证明细节。

由此不能继续把“传统APSP假设仍成立”作为未经标注的当前困难性依据。另一方面，既有细粒度归约没有失效：它们也能传递新算法。关于原始在线布尔矩阵向量任务的OMv猜想理路在线布尔矩阵向量猜想OMvOnline Matrix-Vector Multiplication conjecture · OMv conjecture · 在线矩阵向量乘法猜想固定逐轮布尔乘积的OMv猜想，并通过源边更新及小块重组，推导有预处理费用的动态可达条件下界。则有不同信息接口，不能因另一种带hint矩形变体的变化一并宣布解决。

终点任务要求交三层图、各次倍增的允许步数和一条实际见证，再分别报告值输出成本、可选见证成本、oracle替换后的指数节省。