12

わかりました、この演習のためにこの質問を投稿しました：

ダイクストラのアルゴリズムを変更して、最小値を最大値に変更することで、単一ソースの最長パスの問題を解決できますか? もしそうなら、あなたのアルゴリズムが正しいことを証明してください。そうでない場合は、反例を示してください。

この演習またはダイクストラのアルゴリズムに関連するすべてのことについて、グラフに負の重みがないことを前提としています。そうしないと、最短経路問題であっても、負のエッジが存在するとダイクストラが適切に機能しないため、あまり意味がありません。

わかりました、私の直感は私のためにそれに答えました：

はい、変更可能だと思います。

私はちょうど

  1. 距離配列を MININT に初期化します
  2. distance[w] > distance[v]+weightに変更distance[w] < distance[v]+weight

次に、答えを確認するためにいくつかの調査を行いました。この投稿を見つけました：

ソースから DAG 内の特定のノードまでの最長パス

最初に、上記の投稿のために私の答えが間違っていると思いました。しかし、上記の投稿の答えが間違っている可能性があることがわかりました。The Single-Source Longest Path ProblemとThe Longest Path Problem を混同しました。

Bellman–Ford アルゴリズムの wiki にも、次のように正しく書かれています。

Bellman–Ford アルゴリズムは、重み付き有向グラフで単一ソースの最短パスを計算します。非負のエッジの重みのみを持つグラフの場合、より高速なダイクストラのアルゴリズムも問題を解決します。したがって、Bellman–Ford は、主にエッジの重みが負のグラフに使用されます。

だから私の答えは正しいと思いますよね？ダイクストラは本当に単一ソースの最長パス問題である可能性があり、私の修正も正しいでしょうか?

4

3 に答える 3

10

いいえ、できません。_

多項式時間で最長経路問題に答えるダイスクトラの修正を見つけることができれば、P=NP

そうでない場合は、反例を示してください。

これは非常に悪いタスクです。反例は、特定の変更が間違っていることを示している可能性がありますが、別の変更は OK である可能性があります。
真実は、最長パスの問題が多項式時間で解けるかどうかはわかりませんが、一般的な仮定は、そうではないということです。

緩和ステップを変更するだけについて：

        A
       / \
      1   2
     /     \
    B<--1---C
edges are (A,B),(A,C),(C,B)

A からの dijkstra は最初に B を選択し、次に B に到達することはありませんdistances。

少なくとも、最小ヒープを最大ヒープに変更する必要もありますが、失敗する別の反例があります。

(1) おそらく、P=NP の場合は可能ですが、可能性は非常に低いです。

于 2012-05-05T14:25:23.330 に答える
6

はい、できます。そして、あなたの答えはほぼ正しいです。1つのことを除いて。

負の重みはないと仮定します。この場合、ダイクストラのアルゴリズムは最長パスを見つけることができません。

しかし、負の重みのみを仮定すると、最長経路を簡単に見つけることができます。正しさを証明するには、すべての重みの絶対値を取るだけで、正の重みを持つ通常のダイクストラのアルゴリズムが正確に得られます。

于 2012-05-05T14:45:27.390 に答える
1

有向非循環グラフでは機能しますが、循環グラフでは機能しません。パスはバックトラックするため、ダイクストラのアルゴリズムではそれを回避する方法はありません

于 2013-10-13T18:13:32.317 に答える