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