Warshall算法

🚀write in front🚀
📜所属专栏：> 算法
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

前言

  Warshall算法是一种经典的图论算法，用于计算给定有向图的传递闭包。在本文中，我们将详细介绍Warshall算法，并通过图例来演示算法的执行过程。

什么是传递闭包？

  在离散数学中，如果存在一个有向图中的节点u可以直接和间接到达另一个节点v，则称u可以到达v。如果对于图中的所有节点对(u,v)，都存在一条从u到v的有向路径，则称该图是传递的。传递闭包则表示所有可达性的集合。

Warshall算法的原理

  在我们写程序计算传递闭包时通常会这样写：

  这样的时间复杂度为O(n^4),为了简化该算法的复杂度，Warshall算法使用动态规划的思想，通过多次迭代，计算有向图的传递闭包。
具体算法：

• 初始化可达矩阵。将可达矩阵的值初始化为邻接矩阵的值。
• 逐步构建可达矩阵。对于每一对顶点i和j，如果存在一条从i到j的路径或者存在一条从i到k的路径和一条从k到j的路径，那么我们就可以说顶点i可达顶点j。

因此，我们可以使用以下公式来逐步构建可达矩阵。

T[i][j]=T[i][j]||(T[i][k]&&T[k][j];

其中，reach[i][j]表示从顶点i是否可达顶点j，k是一个介于1和n之间的中间顶点。

最终可达矩阵即为该图的传递闭包。

完整伪代码：

总结：

  其实简单的说，传递闭包就是让“间接到达”变成直接到达。所以我们通过k遍历了所有的间接情况，通过∪和∩得到了最后的矩阵。

  更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

专栏订阅：
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！