最短路径问题 (3)

10.4 用矩阵角度看 APSP

从前两天的文章可以看得出来，如果我们想要找出从 s 到 t 的最短路径，可以透过枚举中继点 v 的方式来更新最短路径的长度。也就是说 dist(s, t) = min { dist(s, u) + dist(u, t) }。如果我们想像一下把 “+” 看成乘法、取 min { dist(s, 1) + dist(1, t), dist(s, 2) + dist(2, t), … } 这件事情当成是 n 种选择的加法，那麽整个计算过程就跟「矩阵相乘」非常类似。

事实上，我们称这样的矩阵运算为 (min, +)-矩阵相乘 ((min, +)-matrix multiplication)。
这麽一来，我们就可以利用数学式子将最短距离矩阵 D 与相邻矩阵 A 连结再一起：
(这边的相邻矩阵的定义为：如果有一条边从 i 连到 j 且权重为 w(i, j)，那麽会有 A[i, j] = w(i, j) ，如果没有边，那麽 A[i, j] = ∞，也就是定义成无穷大。此外我们定义 A[i, i] = 0，也就是自己走到自己是免费的。)

D = A^{n-1}

普通矩阵乘法(实数域)，是需要 O(n^ω) 次乘法计算的，而 ω 被定义为矩阵乘法常数(matrix multiplication exponent)，已知 2 <= ω <= 2.3728596。这个上界是 2020 年末才出炉的最新结果唷。但是这个 (min, +)-矩阵乘法相当奇怪，因为缺少 "加法反元素" 的关系，没办法简单地套用普通矩阵乘法，而目前大家也还不知道 (min, +)-乘法能否做得比 O(n^2.9999999) 来得快。

APSP是否就只能就此作罢呢？当然不是，明天我们就来看几个例子，利用实数(或是高精确度整数) 的普通矩阵乘法，在某些特殊情形下(比方说，这张图的边都没有权重，权重都是 1 的情形) 求得 APSP。