假定在一个权重函数为 ω 的有向图 G 上运行 Johnson 算法。证明,如果图 G 包含一条权重 为 0 的环路 c,那么对于环路 c 上的每条边 (u, v), ωˆ(u, v) = 0。
时间: 2023-07-15 08:12:07 浏览: 55
在Johnson算法中,对于任意一条边(u, v),我们有:
ωˆ(u, v) = ω(u, v) + h(u) - h(v)
其中,h(x) 表示从源节点到节点 x 的最短距离(使用 Bellman-Ford 算法计算),ω(u, v) 表示边 (u, v) 的权重。
现在假设图 G 包含一条权重为 0 的环路 c,其包含 n 条边,即:
(u1, u2), (u2, u3), ..., (un-1, un), (un, u1)
由于环路 c 的权重为 0,我们有:
ω(u1, u2) + ω(u2, u3) + ... + ω(un-1, un) + ω(un, u1) = 0
将上述等式代入 ωˆ(u, v) 的公式中,我们有:
ωˆ(u1, u2) + ωˆ(u2, u3) + ... + ωˆ(un-1, un) + ωˆ(un, u1) = (ω(u1, u2) + h(u1) - h(u2)) + (ω(u2, u3) + h(u2) - h(u3)) + ... + (ω(un-1, un) + h(un-1) - h(un)) + (ω(un, u1) + h(un) - h(u1))
= (ω(u1, u2) + h(u1)) - (h(u2) - ω(u2, u3)) + ... + (h(un-1) - ω(un-1, un)) + (ω(un, u1) + h(un))
= (ω(u1, u2) + h(u1)) - (ω(u2, u3) + h(u3)) + ... + (ω(un-1, un) + h(un-1)) - (ω(un, u1) + h(u1))
= 0
因此,我们得到了一个等式,其中所有的 ωˆ(u, v) 均为 0。即,对于环路 c 上的每条边 (u, v),都有 ωˆ(u, v) = 0。证毕。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)