java - 具有列表列表的 Floyd-Warshall 算法实现

Question

我想使用 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;
    }

Answer 1

您的代码和数据存在许多问题。

• 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？真的吗？

• 为什么最短指的是距离？既然您要修改 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)));
      } 
    } 
  }