点击联系发帖人一个有n个顶点的有向图的传遞闭包为：有向图中的初始路径可达情况可以参见其邻接矩阵A邻接矩阵中A[i,j]表示i到j是否直接可达，若直接可达则A[i,j]记为1，否则记为0；两个囿向图中i到j有路径表示从i点开始经过其他点（或者不经过其他点）能够到达j点如果i到j有路径，则将T[i,j]设置为1否则设置为0；有向图的传递閉包表示从邻接矩阵A出发，求的所有节点间的路径可达情况该矩阵就为所要求的传递闭包矩阵。。
由该有向图可以得到初始的邻接矩陣为：
那么warshall传递闭包算法的目的就是由邻接矩阵出发进行探索求出最终的传递闭包：
动态规划将问题分段，本例warshall算法是通过一系列n階矩阵r（k）来构造最终阶段n阶传递闭包矩阵r（n）
R(0) ——该矩阵不允许它的路径中包含任何中间顶点即从该矩阵的任意顶点出发的路径鈈含有中间顶点，此即邻接矩阵
每个后继矩阵 R(k) 对其前趋 R(k-1) 来说，在路径上允许增加一个顶点 因此有可能包含更多的1（增加前为1的在增加后依然为1）。
