有向无环图在常数时间(O(1))中是否存在路径？

Question

我有一些有向无环图。我想找出O(1)中的两个顶点之间是否存在路径。

我想，我需要存储信息，两个节点之间存在多少路径。但我没有提出完整的算法。

Answer 1

假设F(i,j)是从i到j顶点的路径数。最初（我假设图是空的，如果不是这样，可以使用add操作添加所有边）f(I,j)=1，如果I=j，否则0。

若要将边从A添加到B，可以使用以下过程：

for i = 1 .. n
    for j = 1 .. n
        new_f(i, j) = f(i, j) + f(i, a) * f(b, j) //add the number of paths that contain a new edge

其中n是顶点数。

for i = 1 .. n
        for j = 1 .. n
            new_f(i, j) = f(i, j) - f(i, a) * f(b, j) //subtract the number of paths that contian this edge

删除/添加边显然需要O(n^2)时间。存在从A到b的路径当且仅当F(A,b）！=0。

但是，这种解决方案有一个问题：路径的数量可能非常大（大于标准整数类型所能容纳的数量），并且使用任意精度的算术会增加时间复杂性。为了避免这个问题，您可以计算一些大素数的模路径数（但是小到适合标准整数类型）p。这种解决方案可能会产生不正确的结果（路径数可以是0模P，即使它实际上是非零），但是失败的概率很低。为了进一步减少它，可以计算f对几个不同质数的模。