負の重みでダイクストラのアルゴリズムを使用できますか？
止まる！「2点間を際限なく飛び越えて、無限に安い道をたどることができる」と思う前に、私は一方通行の道をもっと考えています。
このアプリケーションは、ポイントのある山岳地帯になります。明らかに、高から低に移動することはエネルギーを消費しません、実際、それはエネルギーを生成します（したがって、負のパスウェイト）！しかし、あなたがチャック・ノリスでない限り、再び戻ることはそのようには機能しません。
すべてのポイントの重みを負ではなくなるまで増やすことを考えていましたが、それが機能するかどうかはわかりません。
グラフに負のサイクル（エッジの重みの合計が負の有向サイクル）が含まれていない限り、任意の2点間の最短経路がありますが、ダイクストラのアルゴリズムはそれらを見つけるようには設計されていません。負のエッジ重みを持つ有向グラフで単一ソースの最短経路を見つけるための最もよく知られているアルゴリズムは、ベルマンフォードアルゴリズムです。ただし、これにはコストがかかります。ベルマンフォード法ではO（| V |・| E |）時間が必要ですが、ダイクストラ法ではO（| E | + | V | log | V |）時間が必要です。これは、両方のスパースで漸近的に高速です。グラフ（EはO（| V |））と密グラフ（EはO（| V | ^ 2））。
山岳地帯の例では（傾斜の上下で重みが異なるため、必然的に有向グラフ）、負のサイクルの可能性はありません。これは、ポイントを離れて、正味のエネルギーゲインでそこに戻ることを意味するためです。 -永久機関を作成するために使用できます。
すべての重みを一定の値だけ増やして負でないようにすると、機能しません。これを確認するために、AからBへの2つのパスがあり、1つは長さ2の単一のエッジを通過し、もう1つは長さ1、1、および-2のエッジを通過するグラフを考えてみます。2番目のパスは短くなりますが、すべてのエッジの重みを2増やすと、最初のパスの長さは4になり、2番目のパスの長さは6になり、最短パスが逆になります。この戦術は、2つのポイント間のすべての可能なパスが同じ数のエッジを使用する場合にのみ機能します。
最適性の証明を読む場合、行われた仮定の1つは、すべての重みが負ではないということです。だから、ありません。バートが推奨するように、グラフに負のサイクルがない場合はベルマンフォードを使用します。
負のエッジは単なる負の数ではないことを理解する必要があります---それはパスのコストの削減を意味します。パスに負のエッジを追加すると、パスのコストが削減されます---このエッジが負ではなくなるように重みをインクリメントすると、その削減プロパティがなくなり、これは異なります。グラフ。
最適性の証明を読むことをお勧めします---既存のパスにエッジを追加すると、パスのコストが増加するだけである（または影響しない）という仮定が重要であることがわかります。
負の重み付きグラフでダイクストラ法を使用できますが、最初に各頂点の適切なオフセットを見つける必要があります。それは本質的にジョンソンのアルゴリズムが行うことです。しかし、ジョンソンはベルマンフォードを使用して重みオフセットを見つけるため、それはやり過ぎでしょう。Johnson'sは、頂点のペア間のすべての最短経路に対応するように設計されています。
実際には、ネガティブパス環境でダイクストラのアルゴリズムを使用するアルゴリズムがあります。これは、すべての負のエッジを削除し、最初にグラフのバランスを取り直すことによって行われます。このアルゴリズムは「ジョンソンのアルゴリズム」と呼ばれます。
それが機能する方法は、グラフ内の他のすべてのノードにトラバースするためのコストが0の新しいノード（たとえばQ）を追加することです。次に、ポイントQからグラフ上でベルマンフォード法を実行し、Qに関する各ノードのコストを取得します。これをq [x]と呼びます。これは、0または負の数（負のパスの1つを使用したため）になります。 ）。
たとえば、a-> -3-> bであるため、これらすべてのノードにコストが0のノードQを追加すると、q [a] = 0、q [b]=-3になります。
次に、次の式を使用してエッジのバランスを取り直します。重み+ q[ソース]-q[宛先]したがって、a->bの新しい重みは-3+ 0-（-3）=0です。他のすべての場合にこれを行います。グラフのエッジを削除してから、Qとその出力エッジを削除して出来上がり！これで、ダイクストラ法を実行できる負のエッジのないリバランスされたグラフができました。
実行時間は、O（nm）[ベルマンフォード] + nx O（m log n）[nダイクストラ法] + O（n ^ 2）[重み計算] = O（nm log n）時間です。
詳細：http：//joonki-jeong.blogspot.co.uk/2013/01/johnsons-algorithm.html
実際には、エッジの重みを変更することでうまくいくと思います。オフセットではなく、ファクターを使用します。距離を測定する代わりに、ポイントAからBまでに必要な時間を測定するとします。
重量=時間=距離/速度
あなたの仕事が本物の山や車/自転車のためであるならば、あなたは物理的なものを使うために傾斜に応じて速度を適応させることさえできます。
はい、最後に1つのステップを追加することでそれを行うことができます。
If v ∈ Q, Then Decrease-Key(Q, v, v.d)
Else Insert(Q, v) and S = S \ {v}.
式ツリーは、すべてのリーフがオペランド（定数または変数）であり、非リーフノードが二項演算子（、、、、、）である二分+木です。このツリーを実装して、次のようなツリーの基本的なメソッドを使用して多項式をモデル化します。-/*^
[20]導関数には、次の規則を使用します。Derivative（constant）= 0 Derivative（x）= 1 Derivative（P（x）+ Q（y））= Derivative（P（x））+ Derivative（Q（y） ）Derivative（P（x）-Q（y））= Derivative（P（x））-Derivative（Q（y））Derivative（P（x）* Q（y））= P（x）* Derivative（Q （y））+ Q（x）* Derivative（P（x））Derivative（P（x）/ Q（y））= P（x）* Derivative（Q（y））-Q（x）* Derivative（ P（x））Derivative（P（x）^ Q（y））= Q（y）*（P（x）^（Q（y）-1））* Derivative（Q（y））