グラフ - ダイクストラシングルソース最長パスの

Question

[OK]を、私はこのために、運動のこの質問を投稿：

我々は最大最小を変更することにより、シングルソースの最長経路問題を解決するためにダイクストラのアルゴリズムを変更することはできますか？もしそうなら、あなたのアルゴリズムが正しいことを証明してください。そうでない場合は、反例を提示する。この運動やダイクストラ法に関連するすべてのもののために

、私はグラフには負の重みが存在しないと仮定します。さもなければ、最短経路問題でさえ、負エッジが存在する場合、Dijkstraは適切に動作することができないのであまり意味がない。

---

[OK]を、私の直感は私のためにそれに答え：

をはい、私はそれを修正することができると思います。

私だけ

1. MININT
に初期化距離アレー
2. 変更distance[w] > distance[v]+weight

distance[w] < distance[v]+weightから

---

は、その後、私は私の答えを確認するために、いくつかの研究をしました。私はこの記事を見つけました：

Longest path between from a source to certain nodes in a DAG

まず、私は私の答えが原因で上記のポストで間違っていたと思いました。しかし、私は、上記のポストの答えが間違っていることが分かった。 シングルソース最長パス問題と最長パス問題が混在しています。

もBellman–Ford algorithmのウィキでは、それが正しく言った：

ベルマン - フォード法は、加重有向グラフにおいて単一始点最短経路を計算します。 負のエッジ重みを持たないグラフでは、Dijkstraのアルゴリズムが高速になると、という問題も解決されます。したがって、Bellman-Fordは主に負のエッジ重みを持つグラフに使用されます。

私の答えは正しいと思いますよね？ Dijkstraは実際にになる可能性があります。シングルソース最長パス問題と私の修正も正しいのですか？

Answer 1

いいえ、私たちはすることはできません - または非常に少なくとも、何の多項式リダクション/変更が知られていません - ダイクストラは多項式時間で実行中longest path problemは、NP-Hardです！

我々は多項式時間で最長経路問題に答えるためにdijsktraするmodficationを見つけることができればそうでない場合、我々は、反例を提供し、P=NP

を導き出すことができます。

これは非常に悪い作業です。カウンターの例では、特定の変更が間違っている場合がありますが、別の変更がOKである可能性があります。
最長パスの問題が多項式時間で解けるかどうかはわかりませんが、一般的な仮定は - そうではありません。

---

だけ緩和工程を変更に関して：Aから

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

ダイクストラは、最初にBを選択し、その後Bが到達可能なことはありません - それはdistancesのセット外のため。

最低でも、最小ヒープを最大ヒープに変更する必要がありますが、それが失敗する理由はさまざまです。

---

（1）恐らく、おそらくP = NPでも可能ですが、それは非常にありそうもありません。

Answer 2

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

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

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

Answer 3

これは有向非循環グラフでは動作しますが、循環グラフでは動作しません。パスはバックトラックとなるので、ダイクストラのアルゴでそれを避ける方法はありません