路径的“长度”是路径中边的数量。
给定一个源顶点和一个目标顶点,我想找到路径数从源顶点到目标顶点的给定长度 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,这会非常慢,我不确定它是否会因大量输入而终止。
所以我需要一种不同的方法来解决这个问题;任何帮助将不胜感激。
最佳答案
所以,这是我记得的一个漂亮的图论技巧。
制作邻接矩阵A
。其中,如果 i
和 j
之间存在边,则 A[i][j]
为 1,否则为 0。
那么,i
和j
之间长度为k
的路径的个数就是[i][j]
A^k 的条目。
因此,要解决此问题,请构建 A
并使用矩阵乘法构造 A^k(此处使用常用的求幂技巧)。然后只需查找必要的条目即可。
编辑:好吧,您需要在矩阵乘法中进行模运算以避免溢出问题,但这是一个小得多的细节。
关于algorithm - 在无向未加权图中查找给定长度的路径数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14272119/