3

Floyd-Warshall アルゴリズムを使用して、2 つの頂点間の最短経路を見つけたいと考えています。マトリックスは 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 とjx です。

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])が、フロイド・ワーシャルは を求めてい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使用してみませんか? それとも のコピーを作成するつもりでしたか?distanceshortestdistance

set以下のコードは、 を変更するために呼び出しArrayList、正しいインデックスを使用するため、Floyd-Warshall を正しく実行します。ただし、距離行列に対して「期待される」結果と呼ばれるものは生成されません。これは、説明したように、期待される結果が意味をなさず、距離行列自体が疑わしいためです。

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

または、ダイクストラのアルゴリズムを使用します

于 2015-08-25T16:21:29.423 に答える