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

Question

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

在我的 class 中，我已经有了一个距离矩阵。我只是想创建 "shortest path" 矩阵。但它不起作用。它填错了我的矩阵。

我真的希望有人能看看这个并解释哪里出了问题。

我的距离矩阵是：

 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

试试这个：

 shortest.get(j).add(i, Math.min(shortest.get(i).get(k) + shortest.get(k).get(j), 
                        shortest.get(i).get(j)));

或者使用Dijkstra算法

Answer 2

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

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 并且它使用了正确的索引。但是，它不会为您的距离矩阵产生您所说的 "expected" 结果，因为正如我所解释的，您的预期结果没有意义并且距离矩阵本身是可疑的。

  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)));
      } 
    } 
  }

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

Floyd-Warshall algorithm implementation with list of lists

java

algorithm

matrix

floyd-warshall