algorithm - 为每个节点计算有向图中特定节点可以到达的节点数

Question

在有向图中(假设它有很多循环)我需要计算每个节点的特定节点可以到达的节点数。我怎样才能用最少的努力做到这一点？我需要使用哪种算法？

注意:我认为这个问题的合理算法应该递归地计算这个数字(比如如果 a 连接到 b，“节点 a”的结果取决于“节点 b”的结果)。

Answer 1

您要查找的算法称为 Floyd-Warshall algorithm ，一个非常好的和高效的动态规划算法。它可用于计算图中每个单独节点可达的节点集(transitive closure)，尽管它更常用于计算从图中每个单独节点到所有其他节点的最短路径。

(编辑:Floyd-Warshall 算法比您使用所需的复杂得多，因为 Floyd 对其进行了一些扩展以计算最短路径。您可能会发现 this page 很有帮助，它仅描述了“Warshall "算法的一部分 - 您需要的部分。)

我碰巧正在上课学习它，并且 table 上有这篇论文。 F-W 的传递闭包版本的递归是:

T(i,j,k) = T(i,j,k-1) ∨ (T(i,k,k-1) ∧ T(k,j,k-1))

其中 T(a,b,c) 为真当且仅当存在从 a 到 b 的路径仅使用图中的前 c 个顶点(您必须给它们任意编号在运行算法之前)。

从直觉上讲，递推表示存在一条从 i 到 j 的路径，使用前 k 个顶点，如果:

• 在 i 和 j 之间有一条直接路径，使用前 k-1 个顶点，或者
• 在 i 和 k 之间有一条路径，在 k 和 j 之间有一条路径，使用前 k-1 个顶点。

您可以用典型的动态规划方式构建 T(i,j,k) 的整个 3 维表，然后计算您想要的源节点上的所有 TRUE 条目(使用最大 k) , 以获得该源节点的传递闭包的大小。

如果你还在听我的拙劣解释，你可以通过一些技巧使算法非常高效:

• 事实证明，您不需要表格中的第 k 个维度；您可以一遍又一遍地覆盖同一行值。现在程序看起来像:

  T(i,j) = T(i,j) || (T(i,k) && T(k,j))

• 如果 T(i,k) 为 0，那么您可以跳过整个过程，因为该步骤不会发生任何变化。

• 如果 T(i,k) 为 1，则新值将为 T(i,j) || T(k,j)。这可以分块完成，因为 block 或在现代处理器上速度非常快。

希望对您有所帮助...