知识卡片
布尔Floyd用或与判断可达
闭包的布尔动态规划令 T^(k)[i,j] 表示只经前 k 个中间点时是否可达。
新值等于旧可达,或 i→k 与 k→j 同时可达;以逻辑或、与替代最小、加法。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第23章 所有结点对的最短路径 · 查看原书依据
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,
参考来源
- 位置:《算法导论(第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