9.4 关於三连通的练习题

这题超难，我把连结放这边就好。
https://acm.timus.ru/problem.aspx?space=1&num=1819

10 最短路径

最短路径的用途相当广泛，大家应该可以随手想出很多应用。
常见的最短路径问题根据需求，可以分成很多种类，比方说单一源点最短路径 (Single Source Shortest Paths, SSSP)、或是所有点对最短路径 (All Pair Shortest Paths, APSP)。今天我们简单描述一个动态规划的概念，可以解决以上两个问题。

10.1 单一源点最短路径 SSSP

给你一个有向图 G，每一条边上有一个权重代表它的距离。在单一源点最短路径问题中，我们给定一个起点 s，目标是计算出从起点 s 到任何图上到的了的地方的最短距离。
首先，不难证明出任何两个点之间的最短路径，可以只由不超过 n-1 条边就可以抵达。这个最短路径所使用的边数，我们通常称之为跳跃 (hop)。

我们可以利用动态规划来描述此事：定义 dp[k, v] 表示使用不超过 k 次跳跃就能从 s 抵达 v 的最短距离。那麽此时会有 dp[k, v] = min{ dp[k-1, u] + weight(u, v) }。也就是说，我们可以透过枚举抵达 v 的前一步是哪个点，来找出到 v 的最短距离。我们可以发现，计算 dp[k, 1..n] 的时候可以直接利用 dp[k-1, 1..n] 的空间。此外，如果我们最终目的是只要找最短距离，不在乎跳跃数的话，我们甚至可以直接更新在当前的 dp[*, v] 表格上，因此这个表格的第一维可以直接拿掉，只要保证我们有对所有边依序更新总共 n-1 轮就可以了。而这个方法便是为 Bellman-Ford 演算法。

这个演算法的时间复杂度是 O(nm)，其中 n 是点数、m 是边数。

10.2 所有点对最短路径 APSP

这个题目的目标，是要回传一个矩阵 A，使得 A[s, t] 表示从 s 到 t 的最短路径长度。类似地，我们可以发现引入跳跃数的概念，定义动态规划表格 dp[k, s, t] 表示从 s 到 t 使用不超过 k 次跳跃的最短路径，一样也可以用前面 Bellman-Ford 的概念找出答案：dp[k, s, t] = min{ dp[k-1, s, u] + weight(u, t) }。但这样计算出来需要的时间是 O(n^2m) 的，在图中有很多条边的时候，比较没有效率。

有没有办法加速呢？有两种加速的方法，一种是预处理这张图，让他的边数变得很稀疏，但是却又保有原本图 G 上面最短路径的结构，这样产生出来的图 H 我们称为图 G 的路长保留图 (distance preservers)。这个保留最短路径结构的方法，在图非常巨大的时候很好用，因为此时我们甚至可以把原图丢掉，降低储存空间但又能达到计算最短路径的目标。我们在未来几天会再次与大家详细介绍。

另一种加速的方法，是每次计算都让跳跃次数加倍：dp[k, s, t] = min{ dp[k/2, s, u] + dp[k/2, u, t] }。由於 k 不超过 n-1，如此一来用每次加倍的方法，我们就只要更新 log(n-1) 次的表格就行了。时间复杂度是 O(n^3 log n)。

Floyd-Warshall 演算法采用了截然不同的动态规划策略：定义 dp[k, s, t] 表示被允许使用编号 1…k 作为中继站时，从 s 到 t 的最短路径长度。此时就会有 dp[k, s, t] = min{ dp[k-1, s, t], dp[k-1, s, k] + dp[k-1, k, t] }，注意到计算一个 dp[k, s, t] 状态需要的时间从 O(n)，变成了常数了！因此时间复杂度漂亮地降至 O(n^3)。