传递闭包和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

所以，我的问题是，哪个答案是正确的，算法是否按照正确的方式工作？

- abc12331231

Answer 1

矩阵的传递闭包公式为(matrix)^2 + (matrix)。按照该公式，我得到了以下答案：并不完全正确，您正在寻找(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; 相当难以阅读 - 不要害怕分行或至少添加一些括号

- amit

---

也许可以这样写：A[i][j] ||= A[i][k] && A[k][j]; - Damien