Jung APIの最短パスアルゴリズムのパフォーマンス

StackOverflow https://stackoverflow.com/questions/3131978

質問

Jung APIを使用して、中程度の大きなグラフ（20〜100ノード）のいくつかのノード間の最短パスを計算します。現在、ノードを繰り返して、単純な「ショートセットパス」関数を使用して2つのノードの最短パスを計算しています。最短パスはすべてアレイリストに入れられます。

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

}

多くのグラフとノードについてこれを計算する必要があるため、計算をスピードアップしたいと思います。私の知る限り、Jung APIではDijkstraだけが利用できます。だから私の質問は次のとおりです。Dijkstraを使用してパフォーマンスを高めることはできますか？他のアルゴリズムはJung APIで利用可能ですか？最短パスのより異なる方法を提供する別のグラフ実装を使用することは理にかなっていますか？

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

役に立ちましたか？

解決

JungのUnweightedShortestPathクラスは、o（n^2）ランタイムを備えた幅最初の検索アルゴリズムを使用しています。 Dijkstraアルゴリズムは、非加重グラフの代わりに加重グラフのみで、本質的に同じように機能するため、ランタイムもO（n^2）です。

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

私の知る限り、それはJungに実装されていませんが、Googleコード検索からそれをつかむことができるかもしれません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top