知识卡片

普通读书笔记卡 · 3663.a

布尔Floyd用或与判断可达

理解等级:中级

闭包的布尔动态规划令 T^(k)[i,j] 表示只经前 k 个中间点时是否可达。

新值等于旧可达,或 i→k 与 k→j 同时可达;以逻辑或、与替代最小、加法。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第23章《所有结点对的最短路径》(OEBPS/chapter023.xhtml,文本字符[20000,25000))。 - 结论依据:原文说明布尔运算替代,并由Art_P719–P721给出初值与递推。 - 原始内容:This method substitutes the logical operations ∨ (logical OR) and ∧ (logical AND) for the arithmetic operations min and + in the Floyd-Warshall algorithm. For i , j , k = 1, 2, … , n , define to be 1 if there exists a path in