17

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

给定一个源顶点和一个目标顶点,我想找到从源顶点到给定长度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,这将非常慢,我不确定它是否会因大量输入而终止。

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

4

3 回答 3

42

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

做一个邻接矩阵A。如果和A[i][j]之间有边,则为 1 ,否则为 0。ij

那么,和k之间的长度路径数就是A^k的入口。ij[i][j]

因此,要解决这个问题,请A使用矩阵乘法构建和构造 A^k(此处适用于求幂的常用技巧)。然后只需查找必要的条目。

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

于 2013-01-11T05:51:25.377 回答
5

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

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

于 2013-04-26T12:33:28.300 回答
2

让我在上面的答案中添加更多内容(因为这是我面临的扩展问题)。扩展问题是

k在给定的无向树中找到长度路径的数量。

A对于图的给定邻接矩阵,解决方案很简单,G找出 A k-1和 A k,然后计算1对角线上方(或下方)元素中 s 的数量。

让我也添加 python 代码。

import numpy as np

def count_paths(v, n, a):
    # v: number of vertices, n: expected path length
    paths = 0    
    b = np.array(a, copy=True)

    for i in range(n-2):
        b = np.dot(b, a)

    c = np.dot(b, a)
    x = c - b

    for i in range(v):
        for j in range(i+1, v):
            if x[i][j] == 1:
                paths = paths + 1

    return paths

print count_paths(5, 2, np.array([
                np.array([0, 1, 0, 0, 0]),
                np.array([1, 0, 1, 0, 1]),
                np.array([0, 1, 0, 1, 0]),
                np.array([0, 0, 1, 0, 0]),
                np.array([0, 1, 0, 0, 0])
            ])
于 2017-10-10T12:30:26.117 回答