java - 传递闭包和 Warshall 算法

Question

我的输入矩阵如下:

0 1 1 0
0 0 1 0
1 0 0 1
0 0 0 0

我的 Warshall 算法代码如下:

int V = A.length;
     for(int k = 0; k < V; k++) {
        for(int i = 0; i < V; i++) {
           for(int j = 0; j < V; j++) {
              A[i][j] = A[i][j] == 1 || A[i][k] == 1 && A[k][j] == 1 ? 1 : 0;
           }
        }
     }

矩阵的传递闭包公式为 (matrix)^2 + (matrix)。按照公式，我得到这个作为答案:

1 1 1 1
1 0 1 1
1 1 1 1
0 0 0 0

使用我之前提到的这段代码，我得到了这个答案:

1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0

那么，我的问题是，哪一个答案是正确的，算法是否以正确的方式工作？

Answer 1

The formula for the transitive closure of a matrix is (matrix)^2 +(matrix). Following the formula, I get this as an answer:

不完全是，您正在寻找 (matrix)^2 + matrix 的传递闭包，这是单个步骤的公式 - 不是整个解决方案.

这意味着，您需要再次应用它，然后进入第二次迭代:

1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0

(因为有一条从0到1的路径)

第三次迭代将应用相同的矩阵，这意味着这是传递闭包。

因此，从这个测试用例来看，算法似乎是正确的。

---

就是说，行 A[i][j] = A[i][j] == 1 || A[i][k] == 1 && A[k][j] == 1 ? 1 : 0; 非常难读，恕我直言 - 不要害怕打破它或至少添加一些括号