python - Warshall 的传递闭包算法(Python)

Question

我正在编写一个程序，该程序使用 Warshall 算法来查找表示关系的矩阵的传递闭包。这是伪代码中算法的链接: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