路径的“长度”是路径中的边数。
给定一个源顶点和一个目标顶点,我想找到从源顶点到给定长度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,这将非常慢,我不确定它是否会因大量输入而终止。
所以我需要一种不同的方法来解决这个问题;任何帮助将不胜感激。