算法导论22.5 Exercises 答案
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)\)。令\(v_1,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)\)。
将这些不等式和\(v_1.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\)。分两个阶段构造一个无限松弛序列，如下：
构造一条从\(s\)负环\(C\)的一条路径。不失一般性，假设从\(s\)到环\(C\)的第一个节点为\(v_1\)。由于一开始调用了
INITIALIZE-SINGLE-SOURCE进行初始化，因此在这条简单路径上，每条边都成功地进行了一次松弛。构造环路\(Q\)：\((v_1,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},v_i)\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,v_k,v_1,\dots,v_{k-1}\)进行了松弛，因此这\(k-1\)条不等式\(v_{j-1}+w(v_{j-1},v_j)\ge v_j.d\)都能正确保持，并且能够取等号。那么由于\(C\)是负环，因此不等式\(v_{i-1}+w(v_{i-1},v_i)\ge v_i.d\)不能再保持，因此此时是可以被松弛的。
因此，这个松弛的顺序为题目所求。