算法导论 22 Problems 答案

22-1

a

在 $E_f$ 中，所有的边都是从标号小的边指向标号大的边，因此构造出无法一个序列 $a_1,a_2,\dots a_k$，使得 $a_1<a_2,a_2<a_3,\dots ,a_{k-1}<a_k,a_k<a_1$ 成立，从而使得 $\mathrm{\forall }i<k(v_{a_i},v_{a_{i+1}})\in E_f\wedge (v_{a_k},v_{a_1})\in E_f$。因此 $E_f$ 是无环的。由于 $\mathrm{\forall }(v_i,v_j)\in E_f,i<j$ 均成立，因此 $⟨v_1,v_2,\dots ,v_{|V|}⟩$ 是 $G_f$ 的一个拓扑序列。

类似的，$E_b$ 中的所有边都是从标号大的指向标号小的，因此 $E_b$ 是无环的。由于 $\mathrm{\forall }(v_i,v_j)\in E_b,i>j$ 均成立，因此 $⟨v_{|V|},v_{|V|-1},\dots ,v_1⟩$ 是 $G_f$ 的一个拓扑序列。

b

不失一般性，目前需要计算从 $v_s$ 到 $v_t$ 的最短路，假设这条最短路为 $v_{b_1},v_{b_2},v_{b_3}\dots ,v_{b_k},b_1=s,b_k=t$。按照路径松弛性质，只有将边穿插着按照顺序 $(v_{b_1},v_{b_2}),(v_{b_2},v_{b_3}),\dots ,(v_{b_{k-1}},v_{b_k})$ 进行松弛，才能得到 $v_t.d=\delta (v_s,v_t)$。

考虑序列 $b_1,b_2,b_3,\dots ,b_k$ 的起伏顺序。可以知道序列 $b$ 的元素两两不同（因为最短路径是一条最短路径）。对于某个 $b_j$，如果 $b_j<b_{j+1}<\cdots <b_{j+k}$，那么中间这 $k$ 条边可以在这一半轮迭代中完成松弛。接下来，如果 $b_{j+k}>b_{j+k+1}>\cdots >b_{j+k+m}$，那么这 $m$ 条边在另一半轮中可以完成松弛。

也就是说，在一轮迭代中，至少可以对 $2$ 条边进行松弛（如果 $b_1>b_2<b_3$，那么第一轮迭代只能松弛 $(v_{b_1},v_{b_2})$ 这条边）。因此，至少需要 $\lceil |V|/2\rceil$ 轮迭代才能保证边 $(v_{b_1},v_{b_2}),(v_{b_2},v_{b_3}),\dots ,(v_{b_{k-1}},v_{b_k})$ 按顺序被松弛完（为达到恰好 $\lceil N/2\rceil$ 轮按顺序完成路径所有边的松弛，假设 $|V|$ 是奇数，$b_1>b_2<b_3,k=|V|$）。

c

上述算法只需要进行 $\lceil |V|/2\rceil$ 遍的松弛操作，每一遍都需要遍历 $G$ 中的所有边 $E$，整个算法的渐进时间复杂度仍然为 $O(V^2+VE)$，因此它没有对 Bellman-Ford 算法的渐进运行时间改善，只是将常数减少到了原来的 ${\displaystyle \frac{1}{2}}$。

22-2

a

令 $x,y,z$ 是 $3$ 个不同的盒子。

根据定义，如果 $x$ 能够放在 $y$ 中，并且 $y$ 能够放在 $z$ 中，那么存在置换 $\pi ,\tau$ 使得 $x_{\pi (1)}<y_1,x_{\pi (2)}<y_2,\dots ,x_{\pi (d)}<y_d$ 和 $y_{\tau (1)}<z_1,y_{\tau (2)}<z_2,\dots ,y_{\tau (d)}<z_d$。那么可以知道 $x_{\pi (\tau (1))}<z_1,x_{\pi (\tau (2))}<z_2,\dots ,x_{\pi (\tau (d))}<z_d$。排列 $\pi (\tau (\cdot ))$ 说明 $x$ 能够放在 $z$ 中，因此传递关系成立。

b

只需要将数组 $x$ 和 $y$ 进行排序，然后对应下标直接进行比较即可。这种比较方式是正确的，对于 $y$ 中最小的元素，应该将 $x$ 中最小的元素分配给它进行比较，否则不是最优。程序由 IS-INSIDE 给出，其时间复杂度为 $O(d\lg d)$、

IS-INSIDE(x, y, d)
  RANDOMIZED-QUICKSORT(x, 1, d)
  RANDOMIZED-QUICKSORT(y, 1, d)
  for i = 1 to d
    if x[i] >= y[i]
      return False
  return True

c

令 $G=(V,E),V=\{B_1,B_2,\dots ,B_n\},(B_i,B_j)\in E$ 当且仅当 $B_i$ 能装在 $B_j$ 中。

那么这个问题就成为了找一条 $G$ 中的最长路径。首先花费 $O(nd\lg d)$ 的时间对 $B$ 中的每个盒子的每个维度进行排序；接下来花费 $O(n^{2}d)$ 的时间判断每一对盒子之间的嵌套关系，从而构建出图 $G$；接下来使用题目 22.2-3 的内容，把一个盒子视为一个节点上的任务，并且花费为 $1$，那么花费 $O(E)=O(n^2)$ 的时间调用子程序 DAG-LONGEST-PATHS' 求出一条最长路径。因此整个算法的时间复杂度为 $O(nd(n+\lg d))$。

LONGEST-SEQUENCE(B, n, d)
  for i = 1 to n
    RANDOMIZED-QUICKSORT(B[i], 1, d)
  V = {B1, B2, ..., Bn}
  E = ∅
  for i = 1 to n
    for j = 1 to n
      if IS-INSIDE(B[i], B[j])
        E = E ∪ {(Bi, Bj)}
  G = (V, E)
  let T, path be new arrays
  for each u in V
    T[u] = 1
  DAG-LONGEST-PATHS'(G, T)
  let Bj be the vertex s.t. Bj.d is maximum
  p = Bj
  while p.d != 0
    INSERT(path, p)
    p = p.π
  // 进行逆序后才能得到这条路径。
  REVERSE(path)
  return path

22-3

a

对不等式两侧取对数 $\lg$，得到：

$\lg R[i_1,i_2]+\lg R[i_2,i_3]+\cdots +\lg R[i_{k-1},i_k]+\lg R[i_k,i_1]>0$

那么再对两端取符号，得到：

$(-\lg R[i_1,i_2])+(-\lg R[i_2,i_3])+\cdots +(-\lg R[i_{k-1},i_k])+(-\lg R[i_k,i_1])<0$

我们构造图 $G=(V,E),V=\{c_1,c_2,\dots ,c_n\},\mathrm{\forall }u,v\in V,(c_i,c_j)\in E,w(c_i,c_j)=-\lg R[i,j]$. 我们通过将 Bellman-Ford 算法作为子程序即可完成判断这个子序列的存在，整个过程由 CURRENCY-CYCLE-PROFIT 给出，其时间复杂度依赖于 Bellman-Ford 算法的实现，为 $O(V^2+VE)=O(V^3)$。

注意到 $G$ 是一个完全图，因此随机选择一个起点 $s$ 即可。

CURRENCY-CYCLE-PROFIT(R, n)
  let vertex set V = {1, 2, ..., n}
  let edge set E = {(1, 2), (1, 3), ..., (n, n - 2), (n, n - 1)}
  let weight function w(⋅, ⋅) = -lg R[⋅, ⋅]
  select s ∈ V randomly
  return not BELLMAN-FORD((V, E), w, s)

b

这道题和题目 22.1-8 基本相同，依旧其构造出的 GET-NEG-CYCLE 作为子程序即可。其时间复杂度为 $O(V^2+VE)=O(V^3)$。

CURRENCY-NEG-CYCLE(R, n)
  let vertex set V = {1, 2, ..., n}
  let edge set E = {(1, 2), (1, 3), ..., (n, n - 2), (n, n - 1)}
  let weight function w(⋅, ⋅) = -lg R[⋅, ⋅]
  select s ∈ V randomly
  return GET-NEG-CYCLE(G, w, s)

22-4

a

本题思路和题目 22.3-9 完全一致。由于路径最大长度为 $|E|$，因此我们可以考虑建立 $|E|+2$ 个槽，其中第 $i$ 个槽防止满足 $v.d=i$ 的节点 $v$，最后一个槽用于放置满足 $u.d=\mathrm{\infty }$ 的节点。假设从一个槽插入和删除节点的时间复杂度均为 $O(1)$，它们通过一个双向链表维护。

随着松弛过程的进行，所有节点只会从后往前进行移动。此外，由于优先队列的出队顺序 $u$ 满足 $u.d$ 是单调不下降的，因此只需要从小到大遍历每个槽即可。这个算法由程序 DIJKSTRA'''' 给出，其时间复杂度为 $O(E+E)=O(E)$。

DIJKSTRA-E(G, w, s)
  INF = |G.E| + 1
  let A[0 : INF] be new array by list
  for each vertex u ∈ G.V - {s}
    u.d = INF
    u.π = NIL
    LIST-INSERT'(A[INF], u)
  s.d = 0
  s.π = NIL
  LIST-INSERT'(A[0], s)
  S = Ø
  k = 0
  for n = 1 to |V|
    while A[k] == NIL
      k = k + 1
    u = A[k].head
    LIST-DELETE'(A[k], u)
    S = S ∪ {u}
    for each vertex v in G.Adj[u]
      if v.d > u.d + w(u, v)
        LIST-DELETE'(A[v.d], v)
        v.π = u
        v.d = u.d + w(u, v)
        LIST-INSERT'(A[v.d], v)

b

本题可以直接使用题目 22.3-9 的代码作为子程序，令 $W=1$ 后，直接调用 DIJKSTRA''(G, 1, w, s) 即可。那么在这题中由于 $|E|\ge |V|-1$，且题目 22.3-9 给出该算法的时间复杂度为 $(WV+E)$，因此时间复杂度为 $O(E)$。

c

可以知道，$w_i(u,v)$ 表示的是 $k$ 比特数 $w(u,v)$ 的高 $i$ 位。如果 $w(u,v)$ 从高到低的第 $i$ 位是 $0$，那么有 $w_i(u,v)=2w_{i-1}(u,v)$；如果是 $1$，那么有 $w_i(u,v)=2w_{i-1}(u,v)+1$。

在以 $w_i(\cdot ,\cdot )$ 作为边权时，假设从 $s$ 到 $u$ 的最短路径为 $v_1,v_2,\dots ,v_k,v_1=s,v_k=v$，那么考虑 ${\delta }_i(s,v)$ 的值，有：

$\begin{array}{rl}{\delta }_i(s,v)& =\sum _{j=2}^k{w}_i(v_{j-1},v_j)\\ & \ge \sum _{j=2}^{k}2w_{i-1}(v_{j-1},v_j)\\ & \ge 2{\delta }_{i-1}(s,v)\end{array}$

在以 $w_{i-1}(\cdot ,\cdot )$ 作为边权时，假设从 $s$ 到 $u$ 的最短路径为 $v_1^{\prime },v_2^{\prime },\dots ,v_k^{\prime },v_1^{\prime }=s,v_k^{\prime }=v$，那么考虑 ${\delta }_{i-1}(s,v)$，有：

$\begin{array}{rl}2{\delta }_{i-1}(s,v)+|V|-1& \ge 2{\delta }_{i-1}(s,v)+k-1\\ & =\sum _{j=2}^k(2w_{i-1}(v_{j-1}^{\prime },v_j^{\prime })+1)\\ & \ge \sum _{j=2}^k{w}_i(v_{j-1}^{\prime },v_j^{\prime })& (A)\\ & \ge {\delta }_i(s,v)\end{array}$

其中步骤 $(A)$ 是应用了 $w_i(u,v)\le 2w_{i-1}(u,v)+1$。

因此，最终有

$$2{\delta }_{i-1}(s,v)\le {\delta }_i(s,v)\le 2{\delta }_{i-1}(s,v)+|V|-1$$

【网上一些论证使用了假设：计算 $w_i$ 所得到的最短路径也是 $w_{i-1}$ 的最短路径。然而这是错误的，可以构造出反例：$G=(V,E),V=\{a,b,c,d,e,f\},E=\{(a,b,1),(b,c,3),(c,d,3),(a,e,2),(e,f,2),(f,d,2)\}$，计算 ${\delta }_1(a,d)$ 和 ${\delta }_2(a,d)$ 的最短路不是一样的】。

d

$\begin{array}{rl}2{\delta }_{i-1}(s,v)-2{\delta }_{i-1}(s,u)& \le 2w_{i-1}(u,v)\\ & \le w_i(u,v)& (B)\end{array}$

其中步骤 $(B)$ 是应用了 $w_i(u,v)\ge 2w_{i-1}(u,v)$。

因此有 ${\hat{w}}_i(u,v)=w_i(u,v)+2{\delta }_{i-1}(s,u)-2{\delta }_{i-1}(s,v)\ge 0$ 成立。

e

在以 ${\hat{w}}_i(\cdot ,\cdot )$ 作为边权时，考虑 ${\hat{\delta }}_i(s,v)$ 的值，有：

$\begin{array}{rl}{\hat{\delta }}_i(s,v)& =\underset{e\in \text{Path}(s,v)}{min}{\hat{w}}_i(e)\\ & =\underset{\begin{array}{c}p:v_1,v_2,\dots ,v_k;\\ v_1=s,v_k=v\end{array}}{min}\{\sum _{j=2}^k(w_i(v_{j-1},w_j)+2{\delta }_{i-1}(s,v_{j-1})-2{\delta }_{i-1}(s,v_j))\}\\ & =\underset{\begin{array}{c}p:v_1,v_2,\dots ,v_k;\\ v_1=s,v_k=v\end{array}}{min}\{\sum _{j=2}^k{w}_i(v_{j-1},w_j)-2{\delta }_{i-1}(s,v)+2{\delta }_{i-1}(s,s)\}\\ & =\underset{\begin{array}{c}p:v_1,v_2,\dots ,v_k;\\ v_1=s,v_k=v\end{array}}{min}\{\sum _{j=2}^k{w}_i(v_{j-1},w_j)\}-2{\delta }_{i-1}(s,v)\\ & ={\delta }_i(s,v)-2{\delta }_{i-1}(s,v)\end{array}$

从而得到 ${\delta }_i(s,v)={\hat{\delta }}_i(s,v)+2{\delta }_{i-1}(s,v)$。

根据题目 22-4-c 的结论，可以得到 $0\le {\hat{\delta }}_i(s,v)\le |V|-1\le |E|$。

f

假设已经计算了 ${\delta }_{i-1}(s,v)$，那么我们可以以 $O(E)$ 的时间构造出所有边的 $\widehat{w_i}$ 值。由于 ${\hat{\delta }}_i(s,v)\le |E|$，因此我们可以使用题目 22-4-a 所提出的算法以 $O(E)$ 的时间计算出 ${\hat{\delta }}_i(s,v)$ 的值。最终通过题目 22-4-f 的结论以 $O(V)$ 的时间计算 ${\delta }_i(s,v)={\hat{\delta }}_i(s,v)+2{\delta }_{i-1}(s,v)$ 的值。

因此迭代 $\lg W$ 轮后，可以计算出所有节点的 $\delta (s,v)$，本题整个过程由程序 DIJKSTRA-W 给出。

// 这里假设所有的函数被新构造出来后，那么所有值都已经记录好，不会随着时间推移而改变。
DIJKSTRA-W(G, s, w)
  W = max{w(u, v) | (u, v) ∈ G.E}
  k = ⌈lg (W + 1)⌉
  let new function w[i](⋅, ⋅⋅) = ⌈w(⋅, ⋅⋅) / 2^i⌉ for i = 1, 2, 3, ..., k
  DIJKSTRA''(G, 1, w[1], s)
  let new function δ[1](s, ⋅) = ⋅.d
  for i = 2 to k
    let new function w'[i](⋅, ⋅⋅) = w[i](⋅, ⋅⋅) + 2 * δ[i - 1](s, ⋅) - 2 * δ[i - 1](s, ⋅⋅)
    DIJKSTRA-E(G, 1, w'[i], s)
    let new function δ[i](s, ⋅) = ⋅.d + 2 * δ[i - 1](s, ⋅)
  for each u ∈ G.V
    u.d = δ[k](s, v)

22-5

a

如果 ${\mu }^{\ast }=0$，也就是说存在一个长度为 $k$ 的环 $⟨e_1,e_2,\dots ,e_k⟩$，满足 ${\displaystyle {\displaystyle \frac{1}{k}}\sum _{i=1}^{k}w(e_i)=0}$。也就是说，这个环的权值和 ${\displaystyle \sum _{i=1}^{k}w(e_i)}$ 是 $G$ 中所有环的权值和最低的，且为 $0$，因此图 $G$ 没有负环。

这意味着，$G$ 中来自 $s$ 的最短路，其边数是来自不超过 $n-1$ 的一条简单路径。对于边数超过 $n-1$ 的最短路径，必定存在一些边权和为 $0$ 的环，去掉这些环，直到成为一条简单路径，并不会影响它仍然是最短路径。

因此从 $0$ 到 $n-1$ 枚举所有恰好包含 $k$ 条边最短路径中的最短的一条，就可以得到从 $s$ 到 $v$ 的最短路径：

$$\delta (s,v)=\underset{k=0}{\overset{n-1}{min}}\{{\delta }_k(s,v)\}$$

b

为证明

$$\underset{k=0}{\overset{n-1}{max}}\left\{{\displaystyle \frac{{\delta }_n(s,v)-{\delta }_k(s,v)}{n-k}}\right\}\ge 0$$

只需要证明

$$\underset{k=0}{\overset{n-1}{max}}\{{\delta }_n(s,v)-{\delta }_k(s,v)\}\ge 0$$

即可，因为 $n-k>0$ 恒成立。

由于 ${\mu }^{\ast }=0$，因此这个图虽然没有负环，但是存在非负环。

如果 ${\delta }_n(s,v)=\mathrm{\infty }$，那么原结论显然成立。如果 ${\delta }_n(s,v)<\mathrm{\infty }$，那么这条路径必定存在一个边权和为 $0$ 的环，去掉之后那么就成为了一条边数小于 $n$ 的最短路径。此外，由于 ${\delta }_n(s,v)$ 是个和 $k$ 无关的值，因此有

$\begin{array}{rl}\underset{k=0}{\overset{n-1}{max}}\{{\delta }_n(s,v)-{\delta }_k(s,v)\}& ={\delta }_n(s,v)-\underset{k=0}{\overset{n-1}{min}}\{{\delta }_k(s,v)\}\\ & ={\delta }_n(s,v)-\delta (s,v)\\ & \ge 0\end{array}$

因此原结论成立。

c

由于 ${\mu }^{\ast }=0$，因此这个图虽然没有负环，也就是说 $\delta (s,v)\ne -\mathrm{\infty },\delta (s,v)\ne -\mathrm{\infty }$。

由于从节点 $u$ 到节点 $v$ 上的简单路径权重为 $x$，因此有 $\delta (s,v)\le \delta (s,u)+x$（否则，按顺序松弛这条路径上的边将会产生矛盾）。类似的原因，由于从节点 $v$ 到节点 $u$ 上的简单路径权重为 $-x$，因此有 $\delta (s,u)\le \delta (s,v)-x$。结合这两条式子，最终得到 $\delta (s,v)=\delta (s,u)+x$。

d

与题目 22-5-b 类似，只需要证明 ${\displaystyle \underset{k=0}{\overset{n-1}{max}}\{{\delta }_n(s,v)-{\delta }_k(s,v)\}=0}$ 即可。

也就是有 ${\displaystyle {\delta }_n(s,v)-\underset{k=0}{\overset{n-1}{min}}\{{\delta }_k(s,v)\}=0}$，即证明 ${\delta }_n(s,v)=\delta (s,v)$。

令 $c$ 是 $G$ 上的某一个最小平均环，那么存在一条从 $s$ 到 $c$ 上某一个节点 $u$ 的一条最短路径 $p$，假设其长度为 $m$。接下来从 $u$ 沿着这个环走 $n-m$ 步，到达另一个节点 $v$。那么由于从 $s$ 走 $n$ 步可以到达节点 $v$，因此 ${\delta }_n(s,v)\ne \mathrm{\infty }$。也就是说，存在一条从 $s$ 到 $v$，且步数为 $n$ 的最短路径 $p^{\prime }$，根据题目 22-5-c 的结论，$p^{\prime }$ 是从 $s$ 到 $v$ 的全局最短路径。由于 $p^{\prime }$ 的长度大于 $n-1$，因此 $p^{\prime }$ 必定经过一些环。又因为 ${\mu }^{\ast }=0$，因此 $p^{\prime }$ 经过的只能是一部分权值和为 $0$ 的环。去掉这些权值和为 $0$ 的所有环后，那么得到一条长度小于等于 $n-1$ 的最短路径 $p^{″}$，令 $k$ 为 $p^{″}$ 的长度，由此得到 ${\delta }_n(s,v)={\delta }_k(s,v)=\delta (s,v)$。从而证明原结论成立。

e

本题的前提是：${\mu }^{\ast }=0$，和题目 22-5-b 以及 22-5-e 一样。

根据题目 22-5-b 的结论：$\mathrm{\forall }v\in V,{\displaystyle \underset{k=0}{\overset{n-1}{max}}\left\{{\displaystyle \frac{{\delta }_n(s,v)-{\delta }_k(s,v)}{n-k}}\right\}\ge 0}$；

以及题目 22-5-e 的结论：对于 $V$ 中在最小平均环上的某个节点 $v$，有 ${\displaystyle \underset{k=0}{\overset{n-1}{max}}\left\{{\displaystyle \frac{{\delta }_n(s,v)-{\delta }_k(s,v)}{n-k}}\right\}=0}$，

可以得到 ${\displaystyle \underset{u\in V}{min}\left\{\underset{k=0}{\overset{n-1}{max}}\left\{{\displaystyle \frac{{\delta }_n(s,v)-{\delta }_k(s,v)}{n-k}}\right\}\right\}=0}$。

f

将 $E$ 中所有边 $e$ 都增加一个常数 $c$ 后，得到新的权重函数 $w^{\prime }(e)=w(e)+t$。令新图中的平均回路权重 ${\mu }^{\prime }$。对于图中任意一个环 $c$，考虑 ${\displaystyle {\mu }^{\prime \ast }=\underset{c}{min}\{{\mu }^{\prime }(c)\}}$，有：

$\begin{array}{rl}{\mu }^{\prime \ast }& =\underset{c}{min}{\mu }^{\prime }(c)\\ & =\underset{c:⟨e_1,e_2,\dots ,e_k⟩}{min}\{{\displaystyle \frac{1}{k}}\sum _{i=1}^k{w}^{\prime }(e_i)\}\\ & =\underset{c:⟨e_1,e_2,\dots ,e_k⟩}{min}\{{\displaystyle \frac{1}{k}}\sum _{i=1}^k(w(e_i)+t)\}\\ & =\underset{c:⟨e_1,e_2,\dots ,e_k⟩}{min}\{t+{\displaystyle \frac{1}{k}}\sum _{i=1}^{k}w(e_i)\}\\ & =t+\underset{c:⟨e_1,e_2,\dots ,e_k⟩}{min}\{{\displaystyle \frac{1}{k}}\sum _{i=1}^{k}w(e_i)\}\\ & =t+{\mu }^{\ast }\end{array}$

也就是说，对于旧图中的所有环 $c$，如果将它们的所有边权都加上 $t$，那么新的平均权重也会增加 $t$，从而得证。

如果使用题目所求事实，同样可得：

$\begin{array}{rl}{\mu }^{\prime \ast }& =\underset{u\in V}{min}\left\{\underset{k=0}{\overset{n-1}{max}}\left\{{\displaystyle \frac{{\delta }_n^{\prime }(s,v)-{\delta }_k^{\prime }(s,v)}{n-k}}\right\}\right\}\\ & =\underset{u\in V}{min}\left\{\underset{k=0}{\overset{n-1}{max}}\left\{{\displaystyle \frac{({\delta }_n(s,v)+nt)-({\delta }_k(s,v)-kt)}{n-k}}\right\}\right\}\\ & =\underset{u\in V}{min}\left\{\underset{k=0}{\overset{n-1}{max}}\{{\displaystyle \frac{{\delta }_n(s,v)-{\delta }_k(s,v)}{n-k}}+t\}\right\}\\ & =\underset{u\in V}{min}\left\{\underset{k=0}{\overset{n-1}{max}}\left\{{\displaystyle \frac{{\delta }_n(s,v)-{\delta }_k(s,v)}{n-k}}\right\}\right\}+t\\ & ={\mu }^{\ast }+t\end{array}$

g

考虑使用动态规划计算出 ${\delta }_k(s,v)(0\le k\le n,v\in V)$ 的所有值。那么可以将 ${\delta }_k(s,v)$ 写成如下状态转移方程：

${\delta }_k(s,v)=\{\begin{array}{rlrl}& 0& & \text{if}k=0\wedge v=s\\ & \mathrm{\infty }& & \text{if}k=0\wedge v\ne s\\ & \underset{u\in V:(u,v)\in E}{min}\{{\delta }_{k-1}(s,u)+w(u,v)\}& & \text{if}k>0\end{array}$

然而，对于 ${\delta }_{k-1}(s,\cdot )$ 中的所有值，可以以 $O(V+E)=O(E)$ 的时间复杂度求出 ${\delta }_k(s,\cdot )$ 中的所有值。迭代 $|V|$ 轮后，那么求出 ${\delta }_k(s,v)$ 这个表的时间复杂度为 $O(VE)$。

得到关于 ${\delta }_k(s,v)$ 的表后，我们只需要暴力枚举表 ${\delta }_k(s,\cdot )$ 上的值，即可得到 ${\displaystyle {\mu }^{\ast }=\underset{u\in V}{min}\left\{\underset{k=0}{\overset{n-1}{max}}\left\{{\displaystyle \frac{{\delta }_n(s,v)-{\delta }_k(s,v)}{n-k}}\right\}\right\}}$ 的值。这个过程需要 $O(V^2)$ 的时间复杂度。

整个算法由过程 MINIMUM-MEAN-WEIGHT-CYCLE 给出，整个过程的时间复杂度为 $O(VE)$。

MINIMUM-MEAN-WEIGHT-CYCLE(G, s, w)
  let δ[0 : |G.V|, 1 : |G.V|] be new table by ∞
  n = |G.V|
  δ[0, s] = 0
  for i = 0 to n - 1
    for each u ∈ G.V
      for each v in G.Adj[u]
        if δ[i + 1, v] > δ[i, u] + w(u, v)
          δ[i + 1, v] = δ[i, u] + w(u, v)
  μ∗ = ∞
  for each v ∈ G.V
    if δ[n, v] != ∞
      t = ∞
      for k = 0 to |G.V| - 1
        if δ[k, v] != ∞
          t = max{t, (δ[n, v] - δ[k, v]) / (n - k)}
      μ∗ = min{μ∗, t}
  return μ∗

22-6

本题使用将使用类似 Bellman-Ford 算法的操作完成。首先需要对所有边按边权从大到小进行排序，这将花费 $O(E\lg E)$ 的时间。

接下来先考虑两种情况：路径中权值先单调上升，再单调下降；或者是先单调下降，再单调上升；对于前者，将对每条边从小到大先进行松弛操作，再从大到小进行松弛；对于后者，情况类似。那么这两种情况所需要的时间开销为 $O(E)$。

接下来考虑这种情况：先单调上升，后单调下降，再单调上升（只是此时上升的值不能超过一开始的第一条边的边权，以维持双调序列的性质）。首先枚举 $s$ 的每条出边 $(s,v)$。那么在这一轮中，先对整张图进行初始化，然后使用边 $(s,v)$ 进行松弛。接下来进行三轮的松弛：第一轮，从小到大枚举所有大于 $w(u,v)$ 的边；第二轮，从大到小枚举所有 $E$ 中的边；第三轮，从小到大枚举所有小于 $w(u,v)$ 的边。由于 $s$ 最多有 $|V|-1$ 条出边，每轮枚举 $E$ 条边，因此这种情况的时间复杂度为 $O(V^2+VE)$。另一种镜像情况和这种情况类似，此处不赘述。

算法 BITONIC-SHORTEST-PATHS 给出了具体过程，按照上面的分析，其时间复杂度为 $O(V^2+VE)$。

// 为了方便，假设G.E输入的是(出点，入点，边权)三元组，并且使用RELAX'子程序进行松弛操作，第三个参数接受的是边权值。
RELAX-ORDER(E, s, e)
  if s <= e
    for i = s to e
      RELAX'(e[i].u, e[i].v, e[i].w)
  else
    for i = s downto e
      RELAX'(e[i].u, e[i].v, e[i].w)

BITONIC-SHORTEST-PATHS(G, s)
  create a single list e of the edges in G.E
  sort the list of edges into monotonically increasing order by weight e[i].w
  // 情况1
  INITIALIZE-SINGLE-SOURCE(G, s)
  RELAX-ORDER(E, 1, |E|)
  RELAX-ORDER(E, |E|, 1)
  for each u ∈ G.V
    u.d' = u.d
  // 情况2
  INITIALIZE-SINGLE-SOURCE(G, s)
  RELAX-ORDER(E, |E|, 1)
  RELAX-ORDER(E, 1, |E|)
  for each u ∈ G.V
    u.d' = min{u.d', u.d}
  for i = 1 to |E| 
    if e[i].u == s
      // 情况3
      INITIALIZE-SINGLE-SOURCE(G, s)
      RELAX-ORDER(E, i, |E|)
      RELAX-ORDER(E, |E|, 1)
      RELAX-ORDER(E, 1, i)
      for each u ∈ G.V
        u.d' = min{u.d', u.d}
      // 情况4
      INITIALIZE-SINGLE-SOURCE(G, s)
      RELAX-ORDER(E, i, 1)
      RELAX-ORDER(E, 1, |E|)
      RELAX-ORDER(E, |E|, i)
      for each u ∈ G.V
        u.d' = min{u.d', u.d}
  // 最终，u.d'代表真正的答案。