1

JUNG APIを使用して、中規模のグラフ（20〜100ノード）の複数のノード間の最短パスを計算します。現在、ノードを反復処理しており、単純な「ShortetsPath」関数を使用して、2つのノードの最短パスを計算しています。最短パスはすべてArrayListに入れられます。

UnweightedShortestPath<Vertex, SEdge> dist = new UnweightedShortestPath<Vertex, SEdge>(undir);
ArrayList<Vertex> tv = new ArrayList<Vertex>(); // contains nodes for shortestpath
ArrayList<Integer> distances = new ArrayList<Integer>(); // for the distances

for (int j = 0; j <tv.size()-1;j++){ //iterate over nodes
Vertex one = tv.get(j);

for (int k = j+1; k<tv.size();k++){ //iterate over next nodes
    Vertex two = tv.get(k);
    Number n = dist.getDistance(one, two);
    int d;
    if (n == null) {
        d = 5000000;
    }
    else {
        d = n.intValue();
    }
    distances.add(d);
}

}

多くのグラフやノードで計算する必要があるため、計算を高速化したいと思います。私の知る限り、JUNGAPIで使用できるのはダイクストラだけです。だから私の質問は次のとおりです：パフォーマンスを向上させるためにダイクストラを使用できますか？JUNG APIで他のアルゴリズムを利用できますか？最短経路に対してより多くの異なる方法を提供する別のグラフ実装を使用することは理にかなっていますか？

これまでのところありがとう:)

4

1 に答える 1

1

JUNGのUnweightedShortestPathクラスは、O（n ^ 2）ランタイムを持つ幅優先探索アルゴリズムを使用します。ダイクストラアルゴリズムは基本的に同じように機能しますが、重み付けされていないグラフではなく重み付けされたグラフに対してのみ機能するため、実行時間もO（n ^ 2）です。

ただし、グラフ内のノードの可能なすべてのペア間の距離に関心があるように見えますが、ペアワイズアプローチを使用しています。したがって、合計実行時間はO（n * n ^ 2）= O（n ^ 3）です。代わりに、Johnsonのアルゴリズム（ http://en.wikipedia.org/wiki/Johnson's_algorithm ）のようなグローバル最短経路アルゴリズムを使用できます。これが実行時O（n ^ 2 * log（n + ne））です。全体的に少し速くなります。

私の知る限り、これはJUNGには実装されていませんが、Googleコード検索から取得できる可能性があります。

于 2010-06-28T13:24:11.617 に答える