在细粒度复杂性的三大关键假设之一中，计算全源最短路径（APSP）在最坏情况下需要立方时间，直到亚多项式因子。我们首次研究了在预测算法范式下的APSP，即学习增强算法。我们提出了一种APSP算法，它将预测作为额外输入（例如，由过去类似实例学习得到的模型），该预测包括导致每对顶点最短“绕行”的顶点集合。该算法的运行时间为 $\mathrm{O}(n^{2.83} + \eta n)$，其中 $\eta$ 表示预测误差，定义为未能计算和认证最短路径长度最优性的顶点对的数量。
当预测误差（多项式地）小于其最大可能值 $n^2$ 时，即当预测至少稍微好于糟糕时，该算法的性能已经是亚立方的。我们基于Chan、Vassilevska Williams和Xu（STOC 2023）提出的确切三角形问题的共非确定性算法，实质上使该算法能够检测非确定性证书中的错误并从中恢复。我们的结果是设计针对已知细粒度下界的学习增强算法的第一步，这些下界是基于APSP假设的。
博主点评： 本文通过引入预测机制，为全源最短路径问题提供了一种新的思路，尤其是在处理复杂度下界时。这种结合学习与算法的创新方法，预示着未来算法设计的广阔前景，值得深入探讨与实践。