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

Question

在有向图中（假设它有很多周期），我需要计算每个节点可以通过特定节点达到的节点数量节点。我怎样才能以最小的努力做到这一点？我需要使用哪种算法？

注意：我认为这个问题的一个合理的算法应该递归地计算这个数字（比如'a节点'的结果取决于'节点b'的结果，如果a连接到b）。

Answer 1

您正在寻找的算法被称为Floyd-Warshall algorithm，这是一个非常好的高效动态编程算法。它可用于计算图中每个单独节点可到达的节点集（transitive closure），但它更常用于计算从图中每个单独节点到所有其他节点的最短路径。 （编辑：Floyd-Warshall算法比你需要的算法更加复杂，因为它已经被Floyd扩展来计算最短路径，你可能会发现this page有帮助，它只描述了“Warshall”算法的一部分 - 你需要的部分。）

我碰巧正在研究它现在上课，并在我的桌子上有纸。对于FW的传递闭包的版本复发是：

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顶点或
• 我和k之间有一条路径，而k和j之间有一条路径，使用第一个k-1顶点。

您可以使用典型的动态编程方式构建T（i，j，k）的整个三维表，然后计算所需的源节点上的所有TRUE条目（使用max 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)。这可以用大块完成，因为现代处理器上的块OR非常快。

希望帮助...