Why can't we apply Dijkstra's algorithm for a graph with negative weights?
5139 次
3 に答える
15
C から D に移動するたびに料金が支払われる場合、A から B への最も安価な経路を見つけるとはどういう意味ですか?
2 つのノード間に負の重みがある場合、「最短パス」は、これらの 2 つのノード間で前後にループすることです。ホップ数が多いほど、パスは「短く」なります。
これはアルゴリズムとは何の関係もありません。すべては、そのような質問に答えることの不可能性と関係があります。
編集：
上記の主張は、双方向リンクを想定しています。全体的に負の重みを持つサイクルがない場合、支払いを受けて永遠にループする方法はありません。
このような場合、ダイクストラのアルゴリズムは失敗する可能性があります。
次の 2 つのパスを検討してください。
- -25 の重みを持つ最終エッジを横切る前に 100 のコストを積み上げ、合計で 75 になる最適なパス、および
- 総コストが 90 で、負の加重エッジがない次善のパス。
ダイクストラのアルゴリズムは、最初に次善のパスを調査し、それが見つかったときに終了を宣言します。最初に見つかったソリューションよりも悪いサブパスをフォローアップすることはありません
于 2010-07-08T03:17:55.937 に答える
2
有向サイクルを持つ有向グラフがあり、その周りの合計「距離」が負の重みであると想像してください。Start 頂点から End 頂点に向かう途中で有向サイクルを通過できる場合は、有向サイクルを任意の回数だけ往復することができます。
つまり、グラフを横切るパスに無限に負の距離を持たせることができます (または事実上)。
ただし、グラフの周りに有向サイクルがない限り、爆発することなくダイクストラのアルゴリズムを使用することができます。
そうは言っても、負の重みを持つグラフがある場合は、Belman-Fordアルゴリズムを使用できます。ただし、このアルゴリズムは汎用性があるため、少し遅くなります。Bellman-Ford アルゴリズムは O(V·E) かかりますが、Dijkstra アルゴリズムは O(E + VlogV) 時間かかります。
于 2012-04-19T02:52:59.860 に答える