知识卡片
BFS正确性排除最小反例
若某点 d 严格大于真实最短距离,取最短距离最小的此类点 v,并看最短路上它的前驱 u。
u 的距离已正确;u 出队时无论 v 是白、灰还是黑,都会推出 v.d≤u.d+1,与假设矛盾。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
Theorem 20.5 (Correctness of breadth-first search) Let G = (V, E) be a directed or undirected graph, and suppose that BFS is run on G from a given source vertex s ∈ V. Then, during its execution, BFS discovers every vertex v ∈ V that is reachable from the source s, and upon termination, v.d = δ(s, v) for all v ∈ V.
参考来源
- 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[20000,30000))。
- 结论依据:定理20.5按最小反例及v的三种颜色逐一排除错误距离。
- 原始内容:Theorem 20.5 (Correctness of breadth-first search) Let G = ( V , E ) be a directed or undirected graph, and suppose that BFS is run on G from a given source vertex s ∈ V . Then, during its execution, BFS discovers every vertex v ∈ V that is reachable from the source s , and upon termination, v.d = δ( s , v ) for all v ∈ V .