传递闭包,最简单的技术是采用 【弗洛伊德算法】
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
1.若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
2.若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。
代码请见：
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024