算法导论23.3 Exercises 答案
23.3-1
在第一步计算出的\(h\)值为：
\(\begin{array}{|l|l|}\hline v&h(v)\\\hline 1&-5\\\hline 2&-3\\\hline 3&0\\\hline 4&-1\\\hline 5&-6\\\hline 6&-8\\\hline \end{array}\)
更新后的\(\hat{w}\)值如下：
\(\begin{array}{|c|c|c|}\hline u&v&\hat{w}(u,v)\\\hline 1&5&0\\\hline 2&1&3\\\hline 2&4&0\\\hline 3&2&5\\\hline 3&6&0\\\hline 4&1&0\\\hline 4&5&8\\\hline 5&2&4\\\hline 6&2&0\\\hline 6&3&18\\\hline \end{array}\)
23.3-2
章节22.4已经解释了，求解差分约束时添加\(v_0\)是为了让节点\(0\)能够到达所有节点，从而保证每个解\(x_i=\delta(0,i)\)能够被正确求出，避免了负环的情况。
这里的\(s\)和差分约束时\(v_0\)的作用是一样的，从\(s\)能够到达\(V\)中的所有节点，并且\(h(v)\)都能够被正确求出，并且同样规避了负环的问题。
23.3-3
在图\(G'=(V\cup\{s\},E')\)中，由于\(\forall v\in V,w(s,v)=0\)，因此从\(s\)到\(v\)存在一条长度为\(0\)的路径。又因为\(G'\)没有负数边权，因此这条路径就是从\(s\)到\(v\)的最短路。也就是说，\(\forall v\in V,h(v)=0\)。因此\(\forall (u,v)\in E,\hat{w}(u,v)=w(u,v)+h(u)-h(v)=w(u,v)\)。
也就是说，\(\hat{w}(\cdot,\cdot)=w(\cdot,\cdot)\)。
23.3-4
这种做法不能保证路径\(p\)是使用权重函数\(w\)时从\(u\)到\(v\)的一条最短路径，当且仅当\(p\)是使用权重函数\(\hat{w}\)时从\(u\)到\(v\)的一条最短路径。
考虑图\(G=(V,E),V=\{a,b,c\},E=\{(a,b),(a,c),(b,c)\},w(a,b)=w(b,c)=w(a,c)=1\)。那么可以计算得\(\displaystyle{w^{\ast}=\min_{e\in E}w(e)=1}\)。
那么得到\(\hat{w}(a,b)=\hat{w}(b,c)=\hat{w}(a,c)=0\)。
使用权重函数\(w\)时，\(a\rightarrow b\rightarrow c\)不是一条从\(a\)到\(c\)的最短路径。但是使用权重函数\(\hat{w}\)时，\(a\rightarrow b\rightarrow c\)是一条从\(a\)到\(c\)的最短路径。
23.3-5
令\(c=(v_0,v_1,v_2,\dots,v_k)\)，其中\(v_0=v_k\)。那么由题意可以知道，\(w(c)=\displaystyle{\sum_{i=1}^k w(v_{i-1},v_i)=0}\)。考虑计算\(\hat{w}(c)\)的值，有
\(\begin{aligned} \hat{w}(c)&=\sum_{i=1}^k \hat{w}(v_{i-1},v_i)\\ &=\sum_{i=1}^k w(v_{i-1},v_i)+h(v_{i-1})-h(v_i)\\ &=h(v_0)-h(v_k)+\sum_{i=1}^k w(v_{i-1},v_i)\\ &=0 \end{aligned}\)
也就是说，在以\(\hat{w}\)作为边权函数时，边权之和仍然为\(0\)。根据\(\hat{w}\)的定义，\(\forall i\in [1,k],\hat{w}(v_{i-1},v_{i})\ge 0\)成立。因此\(\forall i\in [1,k],\hat{w}(v_{i-1},v_{i})= 0\)成立。
23.3-6
考虑图\(G=(V,E),V=\{a,b,c\},E=\{(a,b),(a,c),(b,c)\},w(b,a)=w(b,c)=w(c,a)=1\)。
那么当以\(a\)作为原点时，运行Bellman-Ford算法，将会无法正确计算出\(h(b)\)和\(h(c)\)的值（即\(h(b)=h(c)=\infty\)），从而三条边的\(\hat{w}\)值都无法被正确计算。
使用反证法证明这个结论：考虑图\(G=(V,E)\)，如果\(\exists u,v\in V\)，从\(u\)到\(v\)没有路径。那么以\(u\)为原点对图\(G\)进行Bellman-Ford算法，将会得到\(h(v)=\infty\)，和\(v\)相关的所有边（出边，入边）将会无法计算出\(\hat{w}\)值。
因此，\(\forall u ,v\in V\)，都存在从\(u\)到\(v\)的路径，也就是说，\(G\)是强连通的，这样才能从任意节点出发，都能计算出所有节点的\(h\)值。
运行Bellman-Ford算法后，对于\(\forall (u,v)\in E\)，都有\(h(u)+w(u,v)\ge h(v)\)。对于构造出的\(\hat{w}(u,v)=w(u,v)+h(u)-h(v)\)，是一个满足符合要求的权重函数，其正确性的证明过程和引理23.1完全一致。之后的步骤和原来的都相同，因此这个版本的Johnson算法返回一个正确的结果。