知识卡片

普通读书笔记卡 · 3645.d.1.c

松弛后单边不等式成立

理解等级:中级

每次松弛边(u,v)后都有 v.d≤u.d+w(u,v):若原本不满足就更新为等号,若已满足则保持。

这个局部约束是证明估计沿最短路径收敛的基础。

这张卡片看不懂?

已有反馈 · 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