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

Question

路径的"长度"是路径中的边数.

给定源和目标顶点,我想找到从源顶点到给定长度 k 的目标顶点的路径数.

• 我们可以根据需要多次访问每个顶点,因此如果路径来自a于b:a -> c -> b -> c -> b它被认为是有效的.这意味着可以有循环,我们可以不止一次通过目的地.

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

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

• 由于答案可能非常大,因此应以模数为单位进行报告.

这是我到目前为止所想到的:

我们可以使用广度优先搜索而不将任何顶点标记为访问,在每次迭代时,我们跟踪我们对该路径所需的边数'n_e'和产品 'p'中每个边缘的重复边数路径有.

如果n_e大于k,则搜索搜索应该终止,如果我们以n_e等于k 到达目的地,我们终止搜索并添加p到路径数的计数.

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

我正在考虑的第二种算法类似于使用这种方法的Floyd Warshall的算法.只有我们不需要最短的路径,所以我不确定这是否正确.

我的第一个算法的问题是'K'可以达到1000000000,这意味着我的搜索将一直运行,直到它有10 ^ 9个边缘,n_e边缘计数将在每个级别增加1,这将非常慢,我不确定它会终止大输入.

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

Answer 1

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

建立邻接矩阵A.A[i][j]如果在i和之间存在边缘,则where 为1 j,否则为0.

然后,k在i和之间的长度路径的数量j就是[i][j]A ^ k 的条目.

因此,为了解决这个问题,A使用矩阵乘法构建和构造A ^ k(这里适用于取幂的常用技巧).然后只需查看必要的条目.

编辑:嗯,你需要在矩阵乘法中进行模运算以避免溢出问题,但这是一个小得多的细节.

Answer 2

实际上，A^k 的 [i][j] 条目在每个简单图中显示了完全不同的“步行”，而不是“路径”。我们可以很容易地通过“数学归纳法”来证明。但是，主要问题是在给定图中找到完全不同的“路径”。我们有很多不同的算法要解决，但上限如下：

(n-2) (n-3) ...(nk) 其中“k”是指定路径长度的给定参数。