k-shortestアルゴリズムを実装しているJavaライブラリをお勧めしますか？>ディレクテッドマルチグラフの唯一の最短アルゴリズムではなく、代替方法を検索しますか？k-shortest（代替）パスアルゴリズム、java実装
私はJGraphTしか見つけられませんでしたが、実際にはバグがありました（私が提出した）が、それを修正するのに多くの時間がかかります。 JGraphTを除いて私は小規模な1人のプロジェクトしか見つかりませんでした：/
ORは代替パスを表示するために最短経路を変更するのは難しいでしょうか？
おかげ
2の可能なオプションして、役に立てば幸い：the MascOpt Packageからclass KshortestPath 1.
オプションに適したオプションですk最短パスのJava実装。
ます。また、これは一人の人間の努力のようですが、良い事はアルゴリズムが共有されていることであるcode.google.com からこれを試すことができます。2.オプション：円のランキング - 詳細はこちら（http://www.ohloh.net/p/k-shortest-paths）
。 注：：与えられたグラフのすべてのノードのペア間の最短パスを見つけることは別の問題です。 Dijkstra vs. Floyd-WarshallのこのSOの質問を参照してください。
リッチグラフの場合は、（ダイクストラ）最短経路のわずかな変動 - 最短パスの頂点間の代替パスが若干高価になる傾向があります。
OPはJavaの実装を求められていますが、選択肢があり、Rがオプションであれば、CRANのkBestShortestPathspackageも非常に良いオプションです。
希望に役立ちます。
私はちょうどオプション2を試しました：円のアルゴリズムとそれは不思議に働いた！約400ノード〜1000リンクのグラフの実行時間は、3000ms（JGraphtの実装の場合）からYenのアルゴリズム実装の場合0.3msまで減少しました。ええ、3000 - > 0.3。タイプミスではありません。 – gjain
がある前に同様の要求あったが、StackOverflowの上のすべてのパスを探していました。 Find all paths in a graph with DFS
これは、それが答えではなく、厳密解ではなく、より多くのガイドの
k-shortest pathsを見つけることは関連していますが、代替パスとまったく同じ問題ではありません。良い代替経路はより複雑です。 Have a read他の同様のアプローチが概説される：
プラトー法ビットがhereが示されています。
あなたはドイツ語読みすることが可能であるならば、this lecture is nice：
の下に、おそらくではありません直感でわかるように、選択肢にはほぼ同じ距離や時間が必要です。重要な違いがあるはずです。最初のアイデア：長さと類似点を最小化するパスを見つける。問題：地元の迂回路がある可能性があります。 ローカルoptimumality：6
ページは、私たちは第三基準を導入し、すべての短いサブパスは最短経路である必要があります。
'k'-shortest edge disjointまたはnode disjoint pathsに興味がありますか？まず、最小コスト最大フローアルゴリズムを調べます。 – IVlad