algorithm - 在无向未加权图中查找给定长度的路径数

Question

路径的“长度”是路径中边的数量。

给定一个源顶点和一个目标顶点，我想找到路径数从源顶点到目标顶点的给定长度 k。

• 我们可以根据需要多次访问每个顶点，因此如果从 a 到 b 的路径如下所示:a -> c -> b -> c -> b 它被认为是有效的。这意味着可以有循环，我们可以多次经过目的地。

• 两个顶点可以由多条边连接。因此，如果顶点 a 和顶点 b 由两条边连接，则路径 a -> b 通过边 1 和 a -> b 通过边 2 被认为是不同的。

• 顶点数 N <= 70，路径长度 K <= 10^9。

• 由于答案可能非常大，因此应以某个数字为模进行报告。

到目前为止，这是我的想法:

我们可以使用breadth-first-search在不将任何顶点标记为已访问的情况下，在每次迭代中，我们都会跟踪该路径所需的边数 'n_e' 和路径中每条边的重复边数的 product 'p'有。

如果 n_e 大于 k，搜索应该终止，如果我们到达 n_e 等于 k ​​的目的地，我们终止搜索并添加 p 计算路径数。

我认为我们可以使用深度优先搜索而不是广度优先搜索，因为我们不需要最短路径并且广度优先搜索中使用的 Q 大小可能不够。

我正在考虑的第二个算法类似于 Floyd Warshall's Algorithm。使用 this方法 。只是我们不需要最短路径，所以我不确定这是正确的。

我的第一个算法存在的问题是“K”可以达到 1000000000，这意味着我的搜索将一直运行到它有 10^9 条边，并且 n_e 边数将在每个级别仅增加 1，这会非常慢，我不确定它是否会因大量输入而终止。

所以我需要一种不同的方法来解决这个问题；任何帮助将不胜感激。

Answer 1

所以，这是我记得的一个漂亮的图论技巧。

制作邻接矩阵A。其中，如果 i 和 j 之间存在边，则 A[i][j] 为 1，否则为 0。

那么，i和j之间长度为k的路径的个数就是[i][j] A^k 的条目。

因此，要解决此问题，请构建 A 并使用矩阵乘法构造 A^k(此处使用常用的求幂技巧)。然后只需查找必要的条目即可。

编辑:好吧，您需要在矩阵乘法中进行模运算以避免溢出问题，但这是一个小得多的细节。