0

私は、Javaでダイクストラの最短ルートアルゴリズムを実装するプロジェクトに取り組んでいます。私は自分のプログラムでこのバージョンを使用しました：LINK

私のプログラムはソースを受け取り、次のような出力を提供します。

Distance to PE Hall: 0.0 Path: [PE Hall]

Distance to Reception: 1.0 Path: [PE Hall, Reception]

Distance to Stairs: 3.0 Path: [PE Hall, Stairs]

Distance to Refectory: 7.0 Path: [PE Hall, Stairs, Refectory]

私が本当に必要としているのは、パス内の各ノード間の距離を示す出力です。次に例を示します。

Distance to Refectory: 7.0 Path: [PE Hall 0.0, Stairs 3.0, Refectory 4.0]

-

アップデート

プログラムが各頂点に「前の頂点」変数を追加することでパスを保存することに気づきました。私の出力はまさに私が望む通りですが、パスを繰り返し処理してメソッドが返す距離は正しくありません。

Target = E250 Distance = 0.0 {E250=0.0}
Target = D Distance = 10.0 {E250=0.0, D=10.0}
Target = C250Trans Distance = 35.0 {E250=0.0, C250Trans=10.0, D=10.0}

これが、各ポイント間のパスと距離を含む配列リストを作成するために使用する方法です。

public static ArrayList<String> getShortestPaths(Vertex target)
  {
      ArrayList<String> path = new ArrayList<String>();
      for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
        {   
             path.add(vertex.name + "=" + vertex.getDistFromPrev());
        }
      Collections.reverse(path);
      return path;
  }

そして、頂点クラスに含まれるパス内の各ポイント間の距離を取得するために使用するメソッドは次のとおりです。

 public double getDistFromPrev()
{
    double weight = 0.;
    for(Edge e : adjacencies){
        if(e.target == this.previous){
            weight = e.weight;
        }
    }
    return weight;
}

参照用の距離行列は次のとおりです。

E250-D = 10

D-C250 = 25

誰かが、各頂点のprevious変数を使用してパスを反復処理すると、誤ったエッジ距離が返される理由を明確にしてください。これは非常に役立ちます。

4

2 に答える 2

0

あなたは道を知っています：

PE Hall, Stairs, Refectory

また、パス内のすべての場所までの距離もわかっています。

PE Hall: 0.0 
Reception: 1.0 
Stairs: 3.0 
Refectory: 7.0

ダイクストラは必要な情報を提供します。適切に「フォーマット」する必要があります（たとえば、データを組み合わせた小さなヘルパー関数を作成し、ダイクストラの完了後にヘルパーを呼び出します）。

于 2013-03-26T14:16:51.830 に答える
0

sパスの開始頂点、頂点から頂点までd(v)の距離、パスのエッジとします。次に、の長さはです。あなたの例では、エッジの長さはvse = w->ved(v) - d(w)Stairs -> Refectory7.0 - 3.0 = 4.0

于 2013-03-26T14:27:54.863 に答える