算法导论22.5 Exercises 答案

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

22.5-1

以下是所求的另外两棵不同的最短路径树的边集：

  • $E_1={(s,t),(t,y),(y,x),(y,z)}$
  • $E_2={(s,t),(s,y),(y,x),(y,z)}$

22.5-2

令$G=(V,E),V={a,b,c},E={(a,b),(a,c),(b,c)},w(a,b)=0,w(a,c)=w(b,c)=1$。那么可以构造出两棵以$a$为根的不同的最短路径树：

  • $E_1={(a,b),(a,c)}$
  • $E_2={(a,b),(b,c)}$

也就是说，对于边$(a,c)$，它存在一棵最短路径树$T_1=(V,E_1)$中，但不存在$T_2=(V,E_2)$中。

22.5-3

我们定义在无穷上的运算：对于某个数$c$，都有$\infty+c=\infty,-\infty+c=\infty$均成立。

如果从$s$到$u$最短路权重为$\delta(s,u)$，这说明从$s$无法到达$u$。对于$v\in V, (u,v)\in E$，如果$\delta(s,v)\neq \infty$，那么有$\delta(s,u)+w(u,v)>\delta(s,v)$，原结论成立。如果$\delta(s,v)=\infty$，那么$\delta(s,u)+w(u,v)=\infty=\delta(s,v)$，原结论成立。

如果$\delta(s,u)=-\infty$，那么其某个后继节点$v$必定有$\delta(s,v)=-\infty$。因此$\delta(s,u)+w(u,v)=-\infty=\delta(s,v)$，原结论成立。

22.5-4

$v.\pi$的值被改变，当且仅当松弛操作成功，也就是有$u.d+w(u,v)<v.d$时才能成功。

假设现在将$s.\pi$ 修改成非NIL值$u$，那么说明$0=s.d>u.d+w(u,v)$。令$v1,v_2,\dots,v_k,v_1=s,v_k=u$是一条从$s$到$u$的路径。那么对于$i=2,3,\dots,k$，在松弛的时刻，有$v_i.d=v{i-1}.d+w(v{i-1},v_i)$。随着松弛的过程继续进行，可能有$v_i.d\ge v{i-1}.d+w(v_{i-1},v_i)$。

将这些不等式和$v1.d>v_k.d+w(v_k,v_1)$两侧一起相加，并且消去所有$\cdot.d$的项，得到$\displaystyle{\sum{i=2}^kw(v_{i-1},v_i)+w(v_k,v_1)<0}$。并且由于$v_1=s$，因此节点$s$在一个负环上。

22.5-5

令$G=(V,E),V={a,b,c,d},E={(a,b),(a,c),(b,c),(c,d),(d,b)},w(a,b)=w(a,c)=1,w(b,c)=w(c,d)=w(d,a)=0$。

我们令$b.\pi=d,c.\pi=b,d.\pi=c$，那么可以知道$b,c,d$构成了一个环，此时的$G_{\pi}$为所求。因为

  • $a\rightarrow c\rightarrow d\rightarrow b$是从$a$到$b$的一条最短路。
  • $a\rightarrow b\rightarrow c$是从$a$到$c$的一条最短路。
  • $a\rightarrow c\rightarrow d$是从$a$到$d$的一条最短路。

22.5-6

通过在松弛过程中使用归纳法来进行证明。

在基础情况下，$V_\pi$中只有$s$，然而从$s$到自身存在路径。

现在假设进行多次松弛后，对于$u\in V\pi$，从$s$到$u$都有一条路径。现在对$(u,v)$进行松弛，并且$v\not\in V{\pi}$。那么此时$v.d=\infty$，也就是说松弛操作必定成功，随后有$v.\pi=u$。松弛完成后，根据归纳假设，从$s$到$u$有一条路径，现在通过边$(u,v)$，从$s$到$v$也有一条路径，并且$v$被纳入$V_\pi$中。

因此，对于$\forall v\in V\pi,G{\pi}$存在一条路径从$s$到$v$中。

22.5-7

当构造好$G$的前驱子图$G\pi=(V,E\pi)$后，对$G\pi$进行BFS，可以证明边的BFS序列为所求松弛序列。将使用归纳法完成证明，假设$u.d’$是从$s$到$u$在$G{\pi}$中的路径的边的数量。可以知道，$s.d’=0$。

  • 满足$u.d’=0$节点仅有一个，为$s$，此时已经满足$s.d=\delta(s,s)$成立。

  • 假设对于某个$d’>0$，对于所有满足$u.d’< d’$的节点，都已经完成了松弛（即$u.d=\delta(s,u)$），现在正在对$u.d’=d’$的节点进行松弛，可以知道$u.\pi.d’=d’-1$，此时已经有$u.\pi.d=\delta(s,v.\pi)$，并且访问$u$在访问$u.\pi$之后，现在通过对边$(u.\pi,u)$对$u$进行松弛，那么根据收敛性质，有$v.d=\delta(s,v)$。

因此边的BFS序列为原答案所求。

22.5-8

假设从$s$可达的一个负环为$C=(v_0,v_1,v_2,\dots,v_k)$，其中$v_0=v_k$。分两个阶段构造一个无限松弛序列，如下：

  1. 构造一条从$s$负环$C$的一条路径。不失一般性，假设从$s$到环$C$的第一个节点为$v_1$。由于一开始调用了INITIALIZE-SINGLE-SOURCE进行初始化，因此在这条简单路径上，每条边都成功地进行了一次松弛。

  2. 构造环路$Q$：$(v1,v_2),(v_2,v_3),\dots,(v{k-1},v_k),(v_k,v_1)$。

那么构造出来的无限松弛序列即为$P+Q+Q+Q+\dots$

由于存在负环，因此这$k$条不等式不能同时成立：$v{i-1}+w(v{i-1},vi)\ge v.d$，对于$i=1,2,\dots,k$。$v{i-1}+w(v_{i-1},v_i)\ge v.d$

考虑使用归纳法证明对$Q$中的边按这个顺序进行重复松弛都能成功。

基础情况是，对$P$中的序列松弛完后，在松弛第一个$Q$的前$k-1$条边时，它们都将一个节点的$d$属性从$\infty$松弛成一个有限值。

归纳步骤是，从第一个$Q$的第$k$条边以及之后，假设现在即将松弛边$(v{i-1},v_i)$，可以发现$v_i$在前$k$次才被松弛过，到现在$v_i.d$还未改变。而$v{i-1}.d$却减少了。由于在之前的第$j=k-1,k-2,\dots,1$次都是分别对$v{i+1},v{i+2},\dots,vk,v_1,\dots,v{k-1}$进行了松弛，因此这$k-1$条不等式$v{j-1}+w(v{j-1},vj)\ge v_j.d$都能正确保持，并且能够取等号。那么由于$C$是负环，因此不等式$v{i-1}+w(v_{i-1},v_i)\ge v_i.d$不能再保持，因此此时是可以被松弛的。

因此，这个松弛的顺序为题目所求。