3

我想使用 Floyd-Warshall 算法来找到两个顶点之间的最短路径。该矩阵位于 ArrayList<ArrayList<Integer>> 中。它总是相当小，例如 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;
    }
4

2 回答 2

3

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

  • 该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)));
      } 
    } 
  }
于 2015-08-25T18:40:25.967 回答
0

试试这个：

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

或者使用 Dijkstra 算法

于 2015-08-25T16:21:29.423 回答