したがって、グラフ内の最長の単純なパスを見つける問題は NP 困難であることを理解しています。これは、エッジの重みを 1 に設定し、最長の単純なパスの長さがエッジ。
私の質問は次のとおりです。グラフを取得し、最大エッジ ウェイト を見つけ、各エッジ ウェイトをmに置き換え、標準の最短パス アルゴリズムを実行した場合、どのようなパスが得られますか? これは明らかに最長の単純なパスではありません。そうであれば、NP = P であり、そのようなものの証明はもう少し複雑な =P になると思います。wm - w
負の重みで最短経路の問題を解くことができれば、最長経路を見つけることができます。この 2 つは同等です。これは、w の代わりに -w の重みを付けることで実行できます。
負の重みの標準アルゴリズムはBellman-Fordアルゴリズムです。ただし、グラフにエッジの合計が負になるようなサイクルがある場合、アルゴリズムは機能しません。作成したグラフでは、そのようなサイクルはすべて負の合計重みを持つため、アルゴリズムは機能しません。もちろん、サイクルがない場合を除きます。その場合、ツリー (またはフォレスト) があり、問題は動的計画法で解決できます。
w の重みを mw に置き換えると、すべての重みが正になることが保証され、標準アルゴリズムを介して最短経路を見つけることができます。このグラフの最短パス P に k 個のエッジがある場合、長さは k*mw(P) です。ここで、w(P) は元の重みを持つパスの長さです。このパスは必ずしも最長のパスではありませんが、k 個のエッジを持つすべてのパスの中で、P が最長のパスです。
代替テキストhttp://dl.getdropbox.com/u/317805/path2.jpg
上のグラフは、アルゴリズムを使用して下のグラフに変換されます。
最長パスは上のグラフの赤い線です。また、タイの切断方法と使用するアルゴリズムに応じて、変換されたグラフの最短パスは青い線または赤い線になります。したがって、前述の定数を使用してグラフのエッジの重みを変換しても、有意な結果は得られません。これが、どんなに賢くても最短経路アルゴリズムを使用して最長経路を見つけることができない理由です。より簡単な変換は、すべてのエッジの重みを無効にしてアルゴリズムを実行することです。私があなたの質問に答えたかどうかはわかりませんが、pathプロパティに関する限り、変換されたグラフには距離に関する有用な情報がありません。
ただし、この特定の変換は他の領域で役立ちます。たとえば、巨大な定数を追加することにより、複数の制約がある場合に、アルゴリズムにバイパトライトマッチングで特定のエッジウェイトを選択させることができます。
