知识卡片
重赋权不改变负环总权
沿环使用势函数重赋权时起点与终点相同,势值增量抵消,环的总权保持不变。因此重赋权既不会制造负环,也无法消除原有负环。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第23章 所有结点对的最短路径 · 查看原书依据
Therefore, any path p from v0 to vk has ŵ(p) = w(p) + h(v0) − h(vk).
参考来源
- 位置:《算法导论(第4版)》第23章《所有结点对的最短路径》(OEBPS/chapter023.xhtml,文本字符[30000,35000))。
- 结论依据:引理23.1的路径势差式与公式图 Art_P741 支持环首尾同点时势值抵消。
- 原始内容:Therefore, any path p from v 0 to v k has ŵ ( p ) = w ( p ) + h ( v 0 ) − h ( v k ).
- 原文勘误:原 XHTML 对环权的展开把末项误印为加号;式(23.11)及 Art_P741 均为减号,本卡按通式与闭环条件核对。
- 公式图核读:`_epub-src/OEBPS/images/Art_P741.jpg`:ŵ(p)=w(p)+h(v₀)−h(vₖ);闭环 v₀=vₖ 时势差为 0。