算法导论22 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 10k 阅读时长 ≈ 9 分钟

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\)成立，从而使得\(\forall i<k (v_{a_i},v_{a_{i+1}})\in E_f\land (v_{a_k},v_{a_1})\in E_f\)。因此\(E_f\)是无环的。由于\(\forall (v_i,v_j)\in E_f,i<j\)均成立，因此\(\langle v_1,v_2,\dots,v_{|V|}\rangle\)是\(G_f\)的一个拓扑序列。

类似的，\(E_b\)中的所有边都是从标号大的指向标号小的，因此\(E_b\)是无环的。由于\(\forall (v_i,v_j)\in E_b,i>j\)均成立，因此\(\langle v_{|V|},v_{|V|-1},\dots,v_{1}\rangle\)是\(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}<\dots<b_{j+k}\)，那么中间这\(k\)条边可以在这一半轮迭代中完成松弛。接下来，如果\(b_{j+k}>b_{j+k+1}>\dots>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算法的渐进运行时间改善，只是将常数减少到了原来的\(\dfrac{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)\)、

1
2
3
4
5
6
7
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^2d)\)的时间判断每一对盒子之间的嵌套关系，从而构建出图\(G\)；接下来使用题目22.2-3的内容，把一个盒子视为一个节点上的任务，并且花费为\(1\)，那么花费\(O(E)=O(n^2)\)的时间调用子程序DAG-LONGEST-PATHS'求出一条最长路径。因此整个算法的时间复杂度为\(O(nd(n+\lg d))\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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]+\dots +\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])+\dots +(-\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\},\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\)即可。

1
2
3
4
5
6
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)\)。

1
2
3
4
5
6
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=\infty\)的节点。假设从一个槽插入和删除节点的时间复杂度均为\(O(1)\)，它们通过一个双向链表维护。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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{aligned} \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{aligned}\)

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

\(\begin{aligned} 2\delta_{i-1}(s,v)+|V|-1&\ge2\delta_{i-1}(s,v)+k-1\\ &=\sum_{j=2}^k (2w_{i-1}(v_{j-1}',v_j')+1)\\ &\ge\sum_{j=2}^k w_{i}(v_{j-1}',v_j')&\qquad(A)\\ &\ge\delta_{i}(s,v) \end{aligned}\)

其中步骤\((A)\)是应用了\(w_i(u,v)\le2w_{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{aligned} 2\delta_{i-1}(s,v)-2\delta_{i-1}(s,u)&\le 2w_{i-1}(u,v)\\ &\le w_i(u,v)&\qquad(B) \end{aligned}\)

其中步骤\((B)\)是应用了\(w_i(u,v)\ge2w_{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{aligned} \hat{\delta}_i(s,v)&=\min_{e\in \text{Path}(s,v)} \hat{w}_i(e)\\ &=\min_{\substack{p:v_1,v_2,\dots,v_k;\\v_1=s,v_k=v}}\left\{\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))\right\}\\ &=\min_{\substack{p:v_1,v_2,\dots,v_k;\\v_1=s,v_k=v}}\left\{\sum_{j=2}^k w_i(v_{j-1},w_{j})-2\delta_{i-1}(s,v)+2\delta_{i-1}(s,s)\right\}\\ &=\min_{\substack{p:v_1,v_2,\dots,v_k;\\v_1=s,v_k=v}}\left\{\sum_{j=2}^k w_i(v_{j-1},w_{j})\right\}-2\delta_{i-1}(s,v)\\ &=\delta_i(s,v)-2\delta_{i-1}(s,v) \end{aligned}\)

从而得到\(\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)\)的时间构造出所有边的\(\hat{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给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 这里假设所有的函数被新构造出来后，那么所有值都已经记录好，不会随着时间推移而改变。
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\)的环\(\langle e_1,e_2,\dots,e_k\rangle\)，满足\(\displaystyle{\dfrac{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)=\min_{k=0}^{n-1}\{\delta_k(s,v)\}\]

b

为证明

\[\max_{k=0}^{n-1}\left\{\dfrac{\delta_n(s,v)-\delta_k(s,v)}{n-k}\right\}\ge 0\]

只需要证明

\[\max_{k=0}^{n-1}\{\delta_n(s,v)-\delta_k(s,v)\}\ge 0\]

即可，因为\(n-k>0\)恒成立。

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

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

\(\begin{aligned} \max_{k=0}^{n-1}\{\delta_n(s,v)-\delta_k(s,v)\}&=\delta_n(s,v)-\min_{k=0}^{n-1}\{\delta_k(s,v)\}\\&=\delta_n(s,v)-\delta(s,v)\\ &\ge 0 \end{aligned}\)

因此原结论成立。

c

由于\(\mu^{\ast}=0\)，因此这个图虽然没有负环，也就是说\(\delta(s,v)\neq-\infty,\delta(s,v)\neq-\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{\max_{k=0}^{n-1}\{\delta_n(s,v)-\delta_k(s,v)\}}=0\)即可。

也就是有\(\displaystyle{\delta_n(s,v)-\min_{k=0}^{n-1}\{\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)\neq \infty\)。也就是说，存在一条从\(s\)到\(v\)，且步数为\(n\)的最短路径\(p'\)，根据题目22-5-c的结论，\(p'\)是从\(s\)到\(v\)的全局最短路径。由于\(p'\)的长度大于\(n-1\)，因此\(p'\)必定经过一些环。又因为\(\mu^{\ast}=0\)，因此\(p'\)经过的只能是一部分权值和为\(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的结论：\(\forall v\in V,\displaystyle{\max_{k=0}^{n-1}\left\{\dfrac{\delta_n(s,v)-\delta_k(s,v)}{n-k}\right\}\ge 0}\)；

以及题目22-5-e的结论：对于\(V\)中在最小平均环上的某个节点\(v\)，有\(\displaystyle{\max_{k=0}^{n-1}\left\{\dfrac{\delta_n(s,v)-\delta_k(s,v)}{n-k}\right\}= 0}\)，

可以得到\(\displaystyle{\min_{u\in V}\left\{\max_{k=0}^{n-1}\left\{\dfrac{\delta_n(s,v)-\delta_k(s,v)}{n-k}\right\}\right\}}=0\)。

f

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

\(\begin{aligned} \mu'^{\ast}&=\min_{c} \mu'(c)\\ &=\min_{c:\langle e_1,e_2,\dots,e_k\rangle} \left\{\dfrac{1}{k} \sum_{i=1}^k w'(e_i)\right\}\\ &=\min_{c:\langle e_1,e_2,\dots,e_k\rangle} \left\{\dfrac{1}{k} \sum_{i=1}^k (w(e_i)+t)\right\}\\ &=\min_{c:\langle e_1,e_2,\dots,e_k\rangle} \left\{t+\dfrac{1}{k} \sum_{i=1}^k w(e_i)\right\}\\ &=t+\min_{c:\langle e_1,e_2,\dots,e_k\rangle} \left\{\dfrac{1}{k} \sum_{i=1}^k w(e_i)\right\}\\ &=t+\mu^{\ast} \end{aligned}\)

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

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

\(\begin{aligned} \mu'^{\ast}&=\min_{u\in V}\left\{\max_{k=0}^{n-1}\left\{\dfrac{\delta_n'(s,v)-\delta_k'(s,v)}{n-k}\right\}\right\}\\ &=\min_{u\in V}\left\{\max_{k=0}^{n-1}\left\{\dfrac{(\delta_n(s,v)+nt)-(\delta_k(s,v)-kt)}{n-k}\right\}\right\}\\ &=\min_{u\in V}\left\{\max_{k=0}^{n-1}\left\{\dfrac{\delta_n(s,v)-\delta_k(s,v)}{n-k}+t\right\}\right\}\\ &=\min_{u\in V}\left\{\max_{k=0}^{n-1}\left\{\dfrac{\delta_n(s,v)-\delta_k(s,v)}{n-k}\right\}\right\}+t\\ &=\mu^{\ast}+t \end{aligned}\)

g

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

\(\delta_k(s,v)= \left \{\begin{aligned} &0 & & \text{if}\quad k=0\land v=s \\ &\infty & & \text{if}\quad k=0\land v\neq s \\ &\min_{u\in V:(u,v)\in E}\{\delta_{k-1}(s,u)+w(u,v)\} & & \text{if}\quad k>0 \\ \end{aligned}\right.\)

然而，对于\(\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}=\min_{u\in V}\left\{\max_{k=0}^{n-1}\left\{\dfrac{\delta_n(s,v)-\delta_k(s,v)}{n-k}\right\}\right\}}\)的值。这个过程需要\(O(V^2)\)的时间复杂度。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 为了方便，假设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'代表真正的答案。