ダイクストラのアルゴリズムを使用して、有向非循環パスで最長パスを見つけることができるかどうかを調べようとしています。負のコスト サイクルがあるため、一般的なグラフでダイクストラの最長パスを見つけることができないことはわかっています。しかし、それはDAGで動作するはずです。Google を通じて、多くの矛盾する情報源を見つけました。すぐに機能すると言う人もいれば、機能しないと言う人もいますが、証明や反例は見つかりませんでした。誰かが私に証明または反例を指摘できますか?
質問する
33145 次
6 に答える
12
私はその問題について考えましたが、一般的には不可能だと思います。非環式であることは十分ではないと思います。
例えば：
このダグでは、a から c に移動したいと考えています。
a - > b - > c
| /\
v |
d - - - - -
dc の長さは 4 です
広告の長さは 1 です
他のすべての長さは 2 です
min 関数を max 関数に置き換えると、アルゴリズムは abc になりますが、最長パスは adc になります。
ダイクストラを使用して最長パスを計算できる特殊なケースが 2 つ見つかりました。
- グラフは有向非巡回であるだけでなく、方向を削除すると非巡回でもあります。言い換えれば、それは木です。ツリーでは、最長パスは最短パスでもあるためです。
- グラフには負の重みしかありません。次に、min の代わりに max を使用して、最長パスを見つけることができます。しかし、これは重みが本当に負の場合にのみ機能します。正の重みを反転するだけでは機能しません。
于 2011-11-10T15:28:09.507 に答える
1
ダイクストラのアルゴリズムを変更して、エッジの重みの反転値を取ることをお勧めします。グラフは非循環であるため、アルゴリズムは無限ループに入らず、負の重みを使用して最適化を続けます。さらに、正の重みが負の値になりますが、繰り返しになりますが、サイクルはありません。これは、訪問したノードの再挿入を許可しない限り、グラフが無向であっても機能します (つまり、負の値を追加する方が常に良いため、2 つのノード間のエンドレス ジャンプを停止します)。
于 2014-05-17T22:57:16.780 に答える
0
唯一の要件は、負のサイクルがないことです。サイクルがない場合は、負の重みから最大の絶対値をすべての重みに追加することで、負のサイクルを再マップできます。そうすれば、すべての重みがゼロ以上になるため、負の重みが失われます。ですから、心配すべき唯一のことを要約すると、負のサイクルが発生しないことです.
于 2011-11-06T14:10:02.040 に答える