图形遍历n步

Question

给出一个简单的无向图,如下所示:

从D,A,B或C(V_start)开始 - 我必须计算从起始点(V_start)到步骤的起始点(V_start)的可能路径数n,其中每个边和顶点可以无限次访问.

我正在考虑进行深度优先搜索,然后停止steps > n || (steps == n && vertex != V_start),但是,如果,例如,这会变得相当昂贵n = 1000000.我的下一个想法让我将DFS与动态编程相结合,然而,这就是我被困住的地方.

(这不是家庭作业,只是为了学习而被困在图表和算法中.)

我怎样才能在一个合理的时间内解决这个问题n呢？

Answer 1

该任务通过矩阵乘法求解.

创建矩阵nX n(为一个单元1包含0和1 mat[i][j],如果有从路径i到j).将此矩阵乘以自身k时间(考虑使用快速矩阵求幂).然后在矩阵的单元格中,mat[i][j]您将获得长度k从开始到i结尾的路径数j.

注意:快速矩阵取幂基本上与快速取幂相同,只是你乘以数字乘以矩阵.

注2:假设n是图中顶点的数量.那么我在这里提出的算法在时间复杂度O(log _k*n ³)中运行并且具有O(n ²)的存储器复杂度.如果您使用此处所述的优化矩阵乘法,您可以进一步改进它.然后时间复杂度将变为O(log _k*n ^{log ₂ 7}).

编辑根据Antoine的要求,我解释了为什么这个算法实际有效:

我将通过归纳证明该算法.归纳的基础是显而易见的:最初我在矩阵中有长度为1的路径数.

让我们假设,直到k我将矩阵提升到kI 的幂的力量,在mat[i][j]长度k介于i和之间的路径数量j.

现在让我们考虑下一步k + 1.很明显,每条长度路径都k + 1包含长度前缀k和一条边.这基本上意味着长度的路径k + 1可以通过(这里我用mat_pow_k矩阵表示提升到kth次幂)来计算

num_paths(X,Y,K + 1)=总和_{I = 0} ^我<n的 mat_pow_k [X] [I]*垫[I] [Y]

再次:n是图中顶点的数量.这可能需要一段时间来理解,但基本上mat[i][y]只有在x和之间存在直接边缘时,初始矩阵在其单元格中才有1 y.并且我们计算这种边缘的所有可能前缀以形成长度路径k + 1.

然而,我写的最后一件事实际上是计算出的k + 1能力mat,这证明了归纳的步骤和我的陈述.