全源最短路的更快做法

· · 休闲·娱乐

:::warning[省流]

近似算法，且复杂度是精度的指数级。

:::

考虑 Floyd 算法，其中的核心转移为

d_{i,j}=\min(d_{i,j},d_{i,k}+d_{k,j})

发现这个和矩阵乘法很像啊！用 \min+ 广义矩阵乘法刻画它。

具体地，记图的邻接矩阵为 A，只需执行 \log 次 A\to A\times A。

使用形如 Strassen 算法之类的 o(n^3) 矩阵乘法即可。

实际上述做法并不可行，因为 Strassen 算法需要用到减法，拓展到 \min+ 广义矩阵乘法就是 \min 的逆元，这是不存在的。

注意到 \dfrac{\ln(e^{\lambda a}+e^{\lambda b})}\lambda 在 \lambda\to-\infty 时趋近 \min(a,b)。

将 \min 替换成这个后矩阵乘法的式子变为

\begin{aligned} C_{i,j}&=\frac1\lambda\sum_k e^{\lambda(A_{i,k}+B_{k,j})}\\ &=\frac1\lambda\sum_k e^{\lambda A_{i,k}}e^{\lambda B_{k,j}} \end{aligned}

只需普通矩阵乘法。