知识卡片
松弛后单边不等式成立
每次松弛边(u,v)后都有 v.d≤u.d+w(u,v):若原本不满足就更新为等号,若已满足则保持。
这个局部约束是证明估计沿最短路径收敛的基础。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第22章 单源最短路径 · 查看原书依据
Lemma 22.13 Let G = (V, E) be a weighted, directed graph with weight function w : E → ℝ, and let (u, v) ∈ E. Then, immediately after edge (u, v) is relaxed by a call of RELAX(u, v, w), we have v.d ≤ u.d + w
参考来源
- 位置:《算法导论(第4版)》第22章《单源最短路径》(OEBPS/chapter022.xhtml,文本字符[60000,65000))。
- 结论依据:引理22.13按更新与不更新两种分支证明松弛后的不等式。
- 原始内容:Lemma 22.13 Let G = ( V , E ) be a weighted, directed graph with weight function w : E → ℝ , and let ( u , v ) ∈ E . Then, immediately after edge ( u , v ) is relaxed by a call of R ELAX ( u , v , w ), we have v.d ≤ u.d + w