知识卡片

普通读书笔记卡 · 3649.e.2.a

BFS正确性排除最小反例

理解等级:高级

若某点 d 严格大于真实最短距离,取最短距离最小的此类点 v,并看最短路上它的前驱 u。

u 的距离已正确;u 出队时无论 v 是白、灰还是黑,都会推出 v.d≤u.d+1,与假设矛盾。

这张卡片看不懂?

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