algorithm - 負の加重グラフにダイクストラ アルゴリズムを使用できますか?

Question

ベルマン フォード アルゴリズムが負の重み付きグラフでうまく機能することは知っていますが、非常にうまく機能するダイクストラ アルゴリズムのコードを開発しました。しかし、負の加重エッジを挿入すると失敗します。解決策はありますか?

Answer 1

あなたが述べたように、Bellman Ford は、負の重みを持つグラフで最短経路を見つけるための最適なアルゴリズムです。このシナリオでダイクストラのアルゴリズムを使用する際の問題は、グラフ内の s から t へのすべての可能なサブパスがゴールのサブパスよりも小さい必要があるとダイクストラが仮定していることです。これは、負のエッジの重みが追加された場合には必ずしも正しくありません。