java - 带列表的Floyd-Warshall算法实现

我想使用Floyd-Warshall算法查找两个顶点之间的最短路径。矩阵位于ArrayList >中。它总是很小，例如4x4或8x8矩阵。

在我的课堂上，我已经有了一个距离矩阵。我只是试图创建“最短路径”矩阵。但这是行不通的。它填补了我的矩阵错误。

我真的希望有人可以看一下并解释问题所在。

我的距离矩阵是:

 0   0  256 411
556  0  558  0
250  0   0  431
 0   0  431  0

测试输出为:

 0   0   0   0
556 556 556 556
250 250 250 250
 0   0   0   0

预期:

500 0 842 681
556 0 806 967
 0  0 500 681
581 0  0  862

我已经注释掉了我的测试输出。 distance是我的矩阵，其顶点之间的距离为整数。在我的矩阵中，i为y，j为x。

public ArrayList<ArrayList<Integer>> calcShortest() {
        //String test = "";
        ArrayList<ArrayList<Integer>> shortest = distance;

        for (int k = 0; k < airports.size(); k++) {
            for (int i = 0; i < airports.size(); i++) {
                for (int j = 0; j < airports.size(); j++) {
                    shortest.get(j).add(i, Math.min(shortest.get(k).get(i) + shortest.get(j).get(k),
                            shortest.get(j).get(i)));
                }
            }
        }
        /*for (int j = 0; j < airports.size(); j++) {
            for (int i = 0; i < airports.size(); i++) {
                test += shortest.get(j).get(i) + " ";
            }
            System.out.println(test);
            test = "";
        }*/
        return shortest;
    }

最佳答案

您的代码和数据有很多问题。

add操作shortest.get(j).add(i, ...)将元素插入ArrayList中。您实际上要设置一个值:shortest.get(j).set(i, ...)

数组索引错误。您正在尝试执行shortest[j][i] = min(shortest[k][i] + shortest[j][k], shortest[j][i])，但是Floyd-Warshall要求使用shortest[i][j] = min(shortest[i][k] + shortest[k][j], shortest[i][j])。

您的预期输出没有意义。 shortest[2][2]怎么可能是500？我们已经知道它是0。如何计算shortest[3][0]是581？您无法从给出的距离矩阵中获得581。

在距离矩阵中，为什么对角线的距离为零？例如，distance[1][3]为0。那么从节点1到节点3的距离为0？真？

为什么要使shortest引用distance？由于您正在修改distance，为什么不只使用distance而不是假装您拥有另一个名为shortest的矩阵？还是您打算复制distance？

下面的代码正确运行Floyd-Warshall，因为它调用set修改ArrayList，并且使用正确的索引。但是，它不会产生您所说的距离矩阵的“预期”结果，因为正如我所解释的，您的预期结果没有意义，并且距离矩阵本身是可疑的。

  int n = shortest.size();
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        shortest.get(i).set(j,
            Math.min(shortest.get(i).get(k) + shortest.get(k).get(j),
                     shortest.get(i).get(j)));
      }
    }
  }