Warshall的传递闭包算法(Python)

Question

我正在编写一个使用Warshall算法的程序来查找表示关系的矩阵的传递闭包.以下是psuedocode中算法的链接:http://people.cs.pitt.edu/~adamlee/courses/cs0441/lectures/lecture27-closures.pdf (第21页).

def warshall(a):

    assert (len(row) == len(a) for row in a)
    n = len(a)
    for k in range (1,n):
        for i in range (1,n):
            for j in range (1,n):
                a[i][j] = a[i][j] or (a[i][k] and a[k][j])


   return M

   print warshall([[0,0,0,1],[1,0,1,0],[1,0,0,1],[0,0,1,0]])

我应该[[1,0,1,1],[1,0,1,1],[1,0,1,1],[1,0,1,1]]

得到[[0,0,0,1],[1,0,1,1],[1,0,1,1],[0,0,1,1]]

Answer 1

在讲座中,索引从1到n,但是在这里,你必须从0到n-1,所以range函数必须是range(0,n)或者更简洁range(n)(也就是说,它return a不是M)

def warshall(a):
    assert (len(row) == len(a) for row in a)
    n = len(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                a[i][j] = a[i][j] or (a[i][k] and a[k][j])
    return a