Floyd-Warshall算法计算有向图的传递闭包

时间:2021-03-05 11:27:11

  Floyd-Warshall算法是用来求解所有结点对最短路径的知名算法,其还有一个重要的用途就是求解有向图的传递闭包,下面就让我来介绍算法导论中关于有向图闭包计算的有关记载吧。

有向图的传递闭包:我们定义图G的传递闭包为图G* = (V, E*);其中E* ={ (i, j) :如果图G中包含一条从结点i到结点j的路径 }。

  实际计算传递闭包时我们可以给G中的每条边赋予权重1,然后运行Floyd-Warshall算法。如果存在一条从结点i -> j的路径,则有dist[i, j] < n;否则,dist[i, j] = INF。

  还有另外一种类似的办法,该算法复杂度与Floyd-Warshall算法类似,但在实际场景中能够节省时间和空间。该办法以逻辑或操作('||')和逻辑与操作('&&')来替换Floyd-Warshall算法中的min和+操作。

  对于i, j, k = 1, 2, ... n, 我们定义:如果图G中存在一条从结点i到结点j的所有中间结点都取自集合{1, 2, ... k}的路径,则t(i, j, k) = 1;否则为0.我们构建传递闭包G* = (V, E*)的方法为:将边(i, j)置于集合E*当且仅当t(i, j, n)为1。

  下面给出算法导论上的伪代码:

Floyd-Warshall算法计算有向图的传递闭包

   就我个人理解而言,给出多组二元关系,对这些二元关系进行标号,用如果三个结点之间满足i - > k, k- > j,则根据传递性就得出了i -> j。我们初始化所有的二元关系,然后利用Floyd-Warshall算法就可以找出所有可以间接得到的二元关系。