java - k-最短（代替）パスアルゴリズム、Java実装

Question

k-shortestアルゴリズムを実装するJavaライブラリをお勧めしますか？>有向マルチグラフで最も短い方法だけでなく、別の方法を検索しますか？

JGraphTしか見つかりませんでしたが、実際にはバグがあります（提出しました）が、修正にはかなりの時間がかかります。他に利用可能な実装はありますか？JGraphTを除いて、私は小さな一人のプロジェクトしか見つけませんでした：/

または、代替パスを表示するためにDisjktra最短パスalgを変更するのは難しいでしょうか？

ありがとう

Answer 1

2可能なオプション：

オプション1.MascOptパッケージclass KshortestPathのfromは、k-shortestパスのJava実装に適したオプションです。

オプション2。code.google.comからも試すことができます。 これは1人の作業のようですが、アルゴリズムが共有されているのは良いことです。円のランキング-詳細はこちらです。（http：//www.ohloh .net / p / k-shortest-paths）

注：特定のグラフ内のノードのすべてのペア間の最短経路を見つけることは、別の問題です。ダイクストラ対フロイド-ウォーシャルに関するこのSOの質問を参照してください。

また、リッチグラフの場合、（ダイクストラ）最短経路のわずかな変化になる傾向があることにも注意してくださいk-shortest paths。最短経路上の頂点間の代替経路であり、コストがわずかに高くなります。

OPがJavaの実装を求めていることは知っていますが、人々に選択肢があり、Rがオプションである場合、CRANのkBestShortestPaths パッケージも非常に優れたオプションです。

お役に立てば幸いです。

Answer 2

k-最短経路の検索は関連していますが、代替経路とまったく同じ問題ではありません。優れた代替パスはより複雑です。他の同様のアプローチが概説されているところを読んでください：

• k-最短経路
• パレート最適性
• プラトー法
• ペナルティアプローチ

プラトー法はここに少し示されています。

あなたがドイツ語を読むことが可能であるならば、この講義は素晴らしいです：

• 例：時間または距離に関する最適化=>問題：興味深い代替案が欠落している
• 分離パス=>同じ問題
• k-最短経路=>問題：実際の代替案はおそらく最初の1000経路の下にはありません

5ページ

したがって、直感は私たちに教えてくれます：代替案はほぼ同じ距離または時間を持っている必要があります。しかし、大きく異なるはずです。したがって、最初のアイデアは、長さと類似性を最小化するパスを見つけることです。問題：ローカル迂回路がある可能性があります。

6ページ

3番目の基準を導入します：局所最適性：すべての短いサブパスは最短経路である必要があります。

Answer 3

以前にも同様のリクエストがありましたが、StackOverflowですべてのパスを探しています。 DFSを使用してグラフ内のすべてのパスを検索する

これがお役に立てば幸いです、それは答えられましたが、正確な解決策ではなく、より多くのガイド