Python中的Warshall算法求传递闭包

Question

我正在写一个程序，使用沃沙尔算法来找到一个矩阵的传递闭包，这个矩阵表示了一种关系。这里有一个算法的伪代码链接：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