Warshall 算法

Warshall算法是一种用于计算有向图的传递闭包的算法。它使用动态规划的思想，通过多次迭代来计算有向图的传递闭包。该算法的时间复杂度为O(n^3)。具体算法步骤如下：

1. 初始化可达矩阵，将可达矩阵的值初始化为邻接矩阵的值。
2. 逐步构建可达矩阵。对于每一对顶点i和j，如果存在一条从i到j的路径或者存在一条从i到k的路径和一条从k到j的路径，那么我们就可以说顶点i可达顶点j。
3. 使用一个嵌套循环，依次遍历每对顶点i和j。对于每对顶点，再次使用一个嵌套循环，依次遍历每个顶点k。
4. 如果顶点j的行i的列为1，就触发关系运算。关系运算的具体步骤是将矩阵j的行k的列和矩阵i的行k的列进行关系运算，并将结果重新赋值给矩阵j的行k的列。
5. 循环结束后，矩阵i表示顶点i到其他所有顶点的可达性，即传递闭包。

Warshall算法通过动态规划的思想，通过多次迭代计算出了有向图的传递闭包，从而简化了计算的复杂度。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [Warshall算法](https://blog.csdn.net/qq_74310471/article/details/129410635)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* [Warshall沃舍尔算法](https://blog.csdn.net/m0_63794226/article/details/124352852)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]