最短路径问题 (5)

10.6 Dijkstra’s SSSP 演算法

如果我们只在乎从某个点 s 出发到所有点的距离，而这张图的所有边权重都是非负的，那麽我们可以使用 Dijkstra 的演算法来解决这个问题。Dijkstra 演算法的核心概念是这样的：我们可以从 s 开始绘制同心圆，并且不断地扩大它直到碰到下一个距离最近的点为止；接着，我们更新这个点相邻的点到 s 的距离，并且继续扩大这个同心圆。当所有点都被碰到的时候，这个演算法便能正确地找出 s 到所有点的最短距离了。

如果我们使用 Fibonacci Heaps 或是 Brodal Queue，那麽理论复杂度可以变成 O(m+n log n)，当图上的边很多的时候，就会变成线性时间。一些相关的实验可以参考：
https://github.com/gabormakrai/dijkstra-performance

10.7 Zwick’s 的有权重 APSP 演算法 Part 1

10.7.1 有权重的 (min, +)-矩阵相乘

如果一个矩阵的每一格的数值都是一个介於 [-M, M] 之间的整数、或是一个代表无穷大的数值；那麽我们可以用普通的矩阵乘法来模拟 (min, +)-矩阵相乘，并且在 Õ(Mn^ω) 的时间内完成(Õ 表示我们省略 log 项)。要怎麽做呢？

假设有两个矩阵 A 和 B，其每一格都是一个介於 [-M, M] 之间的整数，那麽我们可以建立另外两个矩阵 A’ 和 B’，其中 A’[i, j] = (n+1)^(A[i, j] + M)、B’[i, j] = (n+1)^(B[i, j] + M)。(也就是说，我们将负数垫高) 此外，我们将无穷大视为 3M 就可以了。

接着，我们可以用平常的矩阵相乘把 A’ 和 B’ 乘起来，我们假设平常用的电脑，进行加减乘除每一次只能处理 O(log n) 位元，因此对於 C’ = A’ * B’ 矩阵内的每一格，其数值可能高达 n(n+1)^6M 这麽大，要表达这样的数字必须要使用 O(M + log n) 大小的记忆体；对於这样的数字进行加减乘除，大概也需要 Õ(M) 的时间。把 A’ 和 B’ 乘起来的步骤，需要花 Õ(Mn^ω) 的时间。找出 C’ 以後，要怎麽得到真正的 min{ A[i, k] + B[k, j] } 的数值呢？我们注意到，如果最小的 A[i, k]+B[k, j] 是 y，那麽 (n+1)^(y+2M) 必定会整除 C’[i, j]。而且，(n+1)^(y+2M+1) 不会整除 C’[i, j]。因此我们可以用二分搜寻法，在 O(log M) 的时间内找出正确的 y 值。

於是，还原出矩阵 C = A ⋆ B 只要 Õ(Mn^ω) 的时间就好！

有了上述的乘法利器，我们仍然没办法计算最短路径长度。为什麽呢？因为就算每一条边的长度都不超过 L，最短距离出现在矩阵上仍然可能高达 L * n，也就是说套用上述矩阵相乘需要代入 M = L * n，时间复杂度就必定超过 n^3 的 Floyd-Warshall 演算法，相当不划算！

10.7.2 很跳的最短路径可以被 Dijkstra 搞定

对此，我们可以采取折衷的策略：首先，我们先随机挑选 (n/k) log n 个点，其中 k 是一个待定的参数。挑选完毕後，对这些选出来的点 {x1, x2, …}，以它们为起点和终点分别做一次 Dijkstra 演算法，求得从 dist(x, ?) 和 dist(?, x) 的最短路径长度。

还记得我们之前提到的 “跳跃次数” (hops) 吗？不难发现，如果从 s 到 t 的最短路径需要的跳跃数超过 k 的话，有很高的机率，刚才选到的 {x1, x2, …} 其中一个点 x 会出现在 s 到 t 的这条最短路径中间。换句话说，此时的我们只要花费 O(n/k) 时间计算 min_x { dist(s, x) + dist(x, t) } 就能得知 s 到 t 的最短路径了。因为总共有 n^2 个点对，所以我们可以利用 O(mn/k + n^3/k) 的时间在很高的机率下找出所有跳跃次数超过 k 的最短路径。

10.7.3 除了很跳的最短路径以外的部分

至於没那麽跳的最短路径，跳跃次数不超过 k 的，它的路径长也不会超过 kM。因此我们可以用倍增的方法，套用刚才的 (min, +)-矩阵相乘，在 Mn^ω + 2Mn^ω + 4Mn^ω + … + kMn^ω = Õ(kMn^ω) 的时间内就可以搞定它。

因此，如果我们把长跳跟短跳的方法都用上，时间复杂度会是 Õ(kMn^ω + n^3/k)。折衷选定 k 的值，就可以得到一个 Õ(M^0.5 n^((3+ω)/2)) 时间复杂度的最短路径演算法啦！

参考资料：

http://people.csail.mit.edu/virgi/6.890/lecture4.pdf
https://logic.pdmi.ras.ru/ssct09/slides/SSCT09_Uri_Zwick.pdf