知识卡片

普通读书笔记卡 · 3645.a.1.a

不可达顶点估计始终无穷

理解等级:中级

若源点 s 无法到达 v,则 δ(s,v)=∞。

初始化把 v.d 置为∞,后续松弛也不能产生有限源到 v 路径,因此它始终为∞;这与负环可达但权重无下界的−∞不同。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第22章 单源最短路径 · 查看原书依据

      Corollary 22.12 (No-path property) Suppose that in a weighted, directed graph G = (V, E) with weight function w : E → ℝ, no path connects a source vertex s ∈ V to a given vertex v ∈ V. Then, after the graph is

    参考来源

    - 位置:《算法导论(第4版)》第22章《单源最短路径》(OEBPS/chapter022.xhtml,文本字符[60000,65000))。 - 结论依据:推论22.12由上界性质说明不可达顶点估计不可能降成有限值。 - 原始内容:Corollary 22.12 (No-path property) Suppose that in a weighted, directed graph G = ( V , E ) with weight function w : E → ℝ , no path connects a source vertex s ∈ V to a given vertex v ∈ V . Then, after the graph is