(Gabow的单源最短路径伸缩算法) 伸..._

(Gabow的单源最短路径伸缩算法) 伸缩算法解决问题的方式如下:首先考虑相关输人值(如边的权重)的最高有效位，然后通过检查最高两个有效位来对初始解进行微调。这种算法渐次检查更多的最高有效位，每次对解进行微调，直到对所有输入位进行检查并计算出正确解为止。
在本题中，我们通过对边的权重进行伸缩来计算单源最短路径。给定有向图G =(V, E),图的所有边的权重皆为非负整数W。设W= max {w(u, v)}。我们的目标是设计一个运行时间(u,w)∈E为C(E lgW)的算法来计算最短路径。假设所有结点都可以从源结点到达。

该算法对边权重的二迸制表示进行逐位栓査,从最高有效位到最低有效位。具体来说,设k=「Ig(W十1)为W的二迸制表示所需要的位数,并且对于i=1, 2, ., k,设wi(u,v)=lw(u, v)/2-」。也就是说, wi(u,v)是由w(u,v) 的第i个最高有效位给出的“收縮”的w(u, v)版本。 (因此, 対于所有边(u,v)EE,有w(u,v)= Fw(u,v)。)例如,如果k=5, 并且(u,v)=25,其二进制表示内〈11001〉,设w3(u,v)=〈110〉=6。又例如,如果w(u,v)=〈00100〉=4, 则wg(u, v)-〈001〉=1。定 $\delta$ (u,v) 内使用权重函数W;的情况下从节点u到节点ひ的最短路径权重, 设对于所有的节点u, v $\in$ V,有 $\delta$ (u,v）= $\delta$ (u,v)。対于给定源节点s,该伸缩算法首先计算出対于所有节点v $\in$ V的所有最短路径权重w(s, v),然后再计算出w(s, v),这样一直下去, 直到计算出w(s,v)。假定|El $\geq$ |V|一-1, 我们將看到从 $\delta_{i+1}$ 计算出 $\delta_{i}$ ;所需要的时间为O(E),因此,整个算法的运行时间为O(kE)=O(E lgW)。

a.假定対于所有的节点v $\in$ V,有 $\delta$ (s,v)く|El。证明:可以在O(E)的时间内计算出所有的 $\delta$ (s,v) 。
b.证明:可以在O(E)时间内计算出所有的 $\delta$ 1(s,v)。
下面我们来专注于如何从 $\delta_{i+1}$ 计算出 $\delta_{i}$ 。
c.证明：对于i=2, 3, k,要么有wi(u,v)= 2wi-1(u, v),要么有wi(u,v)=2wi-1(u,v)十1。然后再证明:对于所有的节点v $\in$ V,

d.対于所有的(u,v) $\in$ E和i=2, 3, .., k,定义

证明: 对于所有的边(u, v)∈E和i=2， 3，... ， k, 重新计算过的边(u, v) 的权重值wi(u, v)是一个非负整数。
e.在本小题中，我们定义合(s, v) 为使用权重函数wi时从源结点s到结点v的最短路径权重。证明:对于所有的边v∈V和i=2, 3，...，k,有

并且 $\tilde{\delta_{i}}$ (s, v)≤E。
f.说明如何在O(E)时间内从 $\delta$ i-1 (s，v)计算出 $\delta$ i(s, v)，并且得出结论:可以在O(E lgW)时间内计算出所有结点v的 $\delta$ (s, v)。

(Gabow的单源最短路径伸缩算法) 伸...

问题信息

热门推荐

相关试题