知识卡片
不可达顶点估计始终无穷
若源点 s 无法到达 v,则 δ(s,v)=∞。
初始化把 v.d 置为∞,后续松弛也不能产生有限源到 v 路径,因此它始终为∞;这与负环可达但权重无下界的−∞不同。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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