c++ - 图遍历n步

Question

给定一个像这样的简单无向图:

从 D、A、B 或 C (V_start) 开始——我必须计算从起点 (V_start) 到起点有多少条可能的路径n 个步骤的点 (V_start)，其中每条边和顶点都可以无限次访问。

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

(这不是家庭作业，只是我为了学习而被困在玩弄图表和算法。)

如果 n 很大，我该如何在合理的时间内解决这个问题？

Answer 1

这个任务是通过矩阵乘法来解决的。

创建包含 0 和 1 的矩阵 nxn(如果有路径来自i 到 j)。将该矩阵乘以自身 k 次(考虑使用快速矩阵求幂)。然后在矩阵的单元格 mat[i][j] 中，您有长度为 k 的路径数，从 i 开始到 j.

注意:快速矩阵求幂与快速求幂基本相同，只是乘以矩阵而不是数字。

注意 2: 让我们假设 n 是图中的顶点数。那么我在这里提出的算法运行时间复杂度为 O(log _k * n³)，内存复杂度为 O(n ²)。如果按照 here 所述使用优化的矩阵乘法，则可以对其进行更多改进。 .那么时间复杂度就会变成O(log _k * n^log₂7).

---

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

我将通过归纳法证明算法。归纳的基础很明显:最初我在矩阵中有长度为 1 的路径数。

让我们假设直到 k 的幂，如果我将矩阵提高到 k 的幂，我在 mat[i][j] i 和 j 之间长度为 k 的路径数。

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

num_paths(x, y, k + 1) = sum_i=0^{i mat_pow_k[x][i] * mat[i][y]}

同样:n 是图中的顶点数。这可能需要一段时间才能理解，但基本上只有当 x 和 之间有直接边时，初始矩阵的 mat[i][y] 单元格中才为 1 >y。并且我们计算该边的所有可能前缀以形成长度为 k + 1 的路径。

然而我写的最后一件事实际上是计算mat的k + 1次方，这证明了归纳的步骤和我的说法。