Xidian Univ. 最短Walk长度等于最短路径长度的充分必要条 件 定理1：对于式(5-1)的B-F算法（初始条件：对所 有i≠1，有D9=∞)，有： (I)由该算法产生的Dh等于最短（≤h)Walk长度 (2)当且仅当所有不包括节点1的环具有非负的长 度，算法在有限次迭代后结束。此外，如果算法 在最多k≤N次迭代后结束，则结束时Dh就是从i 到1的最短路径长度。 Broadband Wireless Communications Laboratory,Xidian University 11
Broadband Wireless Communications Laboratory, Xidian University 11 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 最短Walk长度等于最短路径长度的充分必要条 件 定理1：对于式（5-1）的B-F算法（初始条件：对所 有 ，有 ），有： ⑴ 由该算法产生的 等于最短（ ）Walk长度 ⑵ 当且仅当所有不包括节点1的环具有非负的长 度，算法在有限次迭代后结束。此外，如果算法 在最多 次迭代后结束，则结束时 就是从i 到1的最短路径长度。 i ≠ 1 = ∞ 0 Di h Di ≤ h k ≤ N h Di
Xidian Univ 定理1中(1)阐明了与最短（≤h)Wak的关系。(2） 阐明了算法何时结束，结束时所得的结果是否是 最短路径。 证明：我们采用归纳法证明（1)。 ①因为D=d1,所以显然有D}等于最短（≤1) 的Walk长度； ②假定D是等于最短（≤h)的Walk长度，求 证D+l是等于最短（≤h+l)的Walk长度。 Broadband Wireless Communications Laboratory,Xidian University 12
Broadband Wireless Communications Laboratory, Xidian University 12 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 定理1中⑴阐明了与最短（ ）Walk的关系。⑵ 阐明了算法何时结束，结束时所得的结果是否是 最短路径。 证明：我们采用归纳法证明（1）。 ① 因为 ，所以显然有 等于最短（ ） 的Walk长度； ② 假定 是等于最短（ ）的Walk长度，求 证 是等于最短（ ）的Walk长度。 ≤ h 1 1 i i D = d 1 Di ≤ 1 h Di ≤ h ≤ h +1 h+1 Di
Xidian Univ 证明： 从到1的最短（≤h+)Walk包含的链路数有两 种情况：一种情况是链路数小于h+1,在此情况 下，有Walk长度等于D；另一种情况是链路数 等于h+1。综上，有 最短（≤h+)Walk长度=min(D,Dl=min{D,mind,+D]} 上1 根据D等于最短（≤h)Walk的假设，对所有 的k≤h有D≤D1。因此有 D=mintdy+D]s minld+D 最短（≤h+l)Walk长度=Dh+l Broadband Wireless Communications Laboratory,Xidian University 13
Broadband Wireless Communications Laboratory, Xidian University 13 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 证明： 从i到1的最短（ ）Walk包含的链路数有两 种情况：一种情况是链路数小于h+1，在此情况 下，有Walk长度等于 ；另一种情况是链路数 等于h+1。综上，有 最短（ ）Walk长度 根据 等于最短（ ）Walk的假设，对所有 的 有 。因此有 最短（ ）Walk长度 ≤ h +1 h Di ≤ h +1 min{ , } min{ ,min[ ]} 1 1 h ij j j h i h i h = Di D = D d + D ≠ + h Di ≤ h k ≤ h −1 ≤ k j k Dj D h i h ij j j h ij j j h Di = d + D ≤ d + D = D + − min[ ] min[ ] 1 1 ≤ h +1 +1 = h Di
Xidian Univ 证明： (2)如果B-F算法在h次迭代后结束，即有 D=D9对所有i和k≥h (5-5) 则我们不可能通过添加更多的链路来减少最短的 Walk长度。（否则，算法没有结束。） 也就是不可能存在一个负长度的（不包括目的节 点)环。因为这样的负长度的任意大次数的重复 将使Walk的长度任意的小，这与式(5-5)相矛 盾。 Broadband Wireless Communications Laboratory,Xidian University 14
Broadband Wireless Communications Laboratory, Xidian University 14 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 证明： （2）如果B-F算法在h次迭代后结束，即有 对所有i和 （5-5） 则我们不可能通过添加更多的链路来减少最短的 Walk长度。（否则，算法没有结束。） 也就是不可能存在一个负长度的（不包括目的节 点）环。因为这样的负长度的任意大次数的重复 将使Walk的长度任意的小，这与式（5-5）相矛 盾。 h i k Di = D k ≥ h
BWC Xidian Univ 证明： 相反，假定所有的不包括1的环具有非负的长度。 从最短（≤）Wak中删除这些环，我们会得到 长度相同或更短的路径。 因此，对每一个和，总存在一条从到1的最短 (≤h)Walk,其相应的最短的路径长度等 于D。 由于路径中没有环，路径可能包括最多N-1条链 路。因此D,=D,-,对所有成立。即算法在最多 N次迭代后结束。 Broadband Wireless Communications Laboratory,Xidian University 15
Broadband Wireless Communications Laboratory, Xidian University 15 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 证明： 相反，假定所有的不包括1的环具有非负的长度。 从最短（ ）Walk中删除这些环，我们会得到 长度相同或更短的路径。 因此，对每一个i和h，总存在一条从i到1的最短 （ ）Walk，其相应的最短的路径长度等 于 。 由于路径中没有环，路径可能包括最多N-1条链 路。因此 ，对所有i成立。即算法在最多 N次迭代后结束。 ≤ h ≤ h h Di −1 = N i N Di D