计算 k 长度的源到目标路径

Question

HERE作者讨论了三种方法来计算k长度的源到目的路径。我无法及时获得基于分而治之方法并声称为 O(V^3logk) 的最后一种方法。

We can also use Divide and Conquer to solve the above problem in O(V^3Logk) time. The count of walks of length k from u to v is the [u][v]’th entry in (graph[V][V])^k. We can calculate power of by doing O(Logk) multiplication by using the divide and conquer technique to calculate power. A multiplication between two matrices of size V x V takes O(V^3) time. Therefore overall time complexity of this method is O(V3Logk).

特别是说

的那一行

The count of walks of length k from u to v is the [u][v]’th entry in (graph[V][V])^k

Answer 1

如果使用邻接矩阵表示图（假设为 M），则 M^k 是表示每对节点之间大小为 k 的路径数的矩阵。您可以使用 O(log k) 矩阵乘法计算 M^k（每次需要 O(V^3) 时间）。

这是一个分而治之的算法，因为要计算 M^k，您可以计算 M' = M^(k/2) 然后 M^k = M' x M'（或 M' x M' x M，如果 k 不能被 2 整除）。

下面是一个用 O(log k) 乘法计算 M^k 的例子：

def matrix_mul(A, B):
    return [[
           sum(x * B[i][col] for i,x in enumerate(row)) for col in range(len(B[0]))
    ] for row in A]

def matrix_pow(M, k):
    if k==1: return M
    M2 = matrix_pow(M, k/2)
    M2 = matrix_mul(M2, M2)

    if k%2==1: M2 = matrix_mul(M2, M)
    return M2

M = [[0,1,1,0,1,0,0,0],
     [0,0,0,0,1,1,0,0],
     [0,0,0,1,0,0,0,0],
     [0,0,0,0,0,1,1,0],
     [0,0,0,0,0,0,0,0],
     [0,0,0,0,1,0,0,0],
     [1,0,1,0,0,0,0,0],
     [0,0,0,1,0,0,0,0]]

for i in range(1, 10):
    print 'Paths from 7 to 2 of size', i, '=', matrix_pow(M, i)[6][1]

输出：

Paths from 7 to 2 of size 1 = 0
Paths from 7 to 2 of size 2 = 1
Paths from 7 to 2 of size 3 = 0
Paths from 7 to 2 of size 4 = 0
Paths from 7 to 2 of size 5 = 1
Paths from 7 to 2 of size 6 = 1
Paths from 7 to 2 of size 7 = 0
Paths from 7 to 2 of size 8 = 1
Paths from 7 to 2 of size 9 = 2

计算 k 长度的源到目标路径

Counting source to destination path of k length

algorithm

graph

divide-and-conquer