2つの頂点の間の最長のパス

Question

私は重み付きエッジを持つ有向グラフを持っています（重みはすべて正です）。

今、私は、2つの与えられた頂点間の最長のパスを見つけるための効率的なアルゴリズムまたはコード（具体的にはC＃）を探しています。

Answer 1

これはすべての負の重みを持つ最短パスアルゴリズムとまったく同じです。これを行うには、負の重みサイクルがないことを確認する必要があります（元の場合は、正の重みサイクルがないことを確認することとおそらく同じです）。最善の策は、重みの逆数を取ってBellman-Fordを実行し、その結果の逆数を取ることです。

Answer 2

QuickGraph projectは、グラフを実装する.NETデータ構造を提供しています。また、このようなデータ構造を操作するアルゴリズムも提供しています。私はあなたが探しているアルゴリズムがライブラリに実装されていると確信しています。

Answer 3

ベルマンフォードが一番長いパスを与えない場合、各頂点はたかだか1回しか出現できない単純なパスを意味しない限り、David Bergerの答えは正しい。ウェイトが正であると言うので、シンプルなパスを意味する場合を除いて、グラフにサイクル（ソースから到達可能）があるときに最も長いパスが存在することはできません。最長単純経路問題はNP完全です。 Wikipediaを参照してください。

だから、有向非循環グラフ（DAG）を意味すると仮定しましょう。線形時間では、u-> vの各uについて、s - > * uから最長の経路を知っているので、開始頂点sから各頂点vまでの最長経路を計算することができます。これは簡単です。有向グラフで深度の最初の検索を行い、頂点の最長パスを訪問した逆の順序で計算することができます。また、3色のマーキングを使用して、DFS全体の後端を検出することもできます（開いたが終了していない頂点は灰色です）。詳細については、もう一度Wikipediaを参照してください。 DAG上の最長/最短パス検出は、（たとえ特定の種類のDAGを仮定していたとしても）ビタビアルゴリズムと呼ばれることがあります。

私は線形時間の動的プログラミングソリューションを最初に試みます。サイクルがあると、Bellman-Fordは問題を解決しません。

Answer 4

私はこれをしばらく探していたので誰にも役立ちますが、見つけることができませんでした。私はQuickGraphを使用して、特定のルールにも合致する最長のパスを見つけなければならなかった問題を解決しました。それは私が最初の結果を得ると、それはブルートフォースで少ししたように非常にエレガントではありませんが、ここにあります。

https://github.com/ndsrf/random/blob/master/LongestSkiPath/LongestSkiPath/SkiingResolver.cs#L129-L161

=あなたはlenghtsで最短を見つけるためにアルゴリズムを使用する最長のパスを取得するには-1。その後、最長のパスを見つけるために、最長のパスからエッジを削除して、問題の条件に基づいて「より良い」最長パスを取得できるかどうかを確認します。