ダイクストラ法が負の重みで正しく動かない理由

ダイクストラ法の中心にあるのは、未確定の頂点のうち始点からの暫定距離が最小の頂点を選び、その距離を確定する操作です。1959年の原論文でも、最短経路が判明した頂点の集合へ距離の小さい順に頂点を加え、終点がその集合に入った時点で解を得る手順として説明されています。

負の重みがなければ貪欲な選択が安全な理由

この選択が安全なのは、あとから別の頂点を経由して距離が小さくならない場合に限られます。すべての辺の重みが0以上なら、未確定の頂点を通る経路ではコストが0以上増えるだけです。そのため、現在の暫定距離が最小の頂点へ、あとからより短い経路が現れることはありません。これがダイクストラ法の貪欲な選択を支える性質です。

辺3本でつくる反例

負の辺が1本あるだけで、この性質は失われます。有向辺 S→A の重みを2、S→B を5、B→A を-4とします。

1959年の手順のように、いったん確定した頂点をあとから修正しない実装は、まず A を距離2で確定します。しかし本当の最短経路は S→B→A で、コストは5+(-4)=1です。最初は遠く見えた B を経由すると、確定済みの A への距離が短くなります。この反例に負閉路は必要ありません。問題は計算そのものではなく、あとで見つかった距離1を確定済みの A に反映しないことです。

実装によって結果が変わる

ただし「ダイクストラ法は負の辺があると必ず誤答する」と言い切るのも正確ではありません。Princeton の Algorithms は、頂点が優先度付きキューに再び入れるかどうかで二つの版を区別しています。再投入を許す版は、負閉路がなければ正しい答えを得られる一方、最悪の場合は実行時間が指数的になります。確定した頂点を二度と処理しない版は、負の辺で誤答することがあります。同じ名前で呼ばれていても、実装がどの不変条件と保証に依存しているかで結果が変わります。優先度付きキューによく使われるヒープの構造は ヒープはソート済みリストではない で扱いました。

負の辺があるときに使う手法

負の辺を含むグラフで単一始点の最短経路を求めるなら、Bellman–Ford法を検討できます。始点から到達可能な負閉路も検出でき、頂点数をV、辺数をEとすると、最悪実行時間はVEに比例します。

グラフがDAG（有向非巡回グラフ）なら、負の辺があってもトポロジカル順に辺を緩和すれば、V+Eに比例する時間で解けます。

到達可能な負閉路があると、それを回るたびに経路のコストが下がります。そのため、その負閉路を経由して到達できる終点には有限の最短経路が存在しません。負の辺があるという事実だけでなく、負閉路が始点から到達可能か、グラフがDAGかも確認すべき理由です。

ライブラリの文書も別に確認する

ライブラリの挙動は、数学上の保証とは分けて確認する必要があります。SciPy のドキュメントは scipy.sparse.csgraph.dijkstra の入力を非負の距離として定義し、負の距離があるとこのルーチンは動作しないため、Bellman–Ford法や Johnson法などを使うよう案内しています（2026年10月4日確認）。別のライブラリが警告、例外、誤った結果のどれを返すかは、利用しているバージョンのドキュメントで確かめてください。

参照したドキュメント

• E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs” (1959)、CWI 保管の PDF
• Robert Sedgewick, Kevin Wayne, Algorithms 4.4 Shortest Paths（Princeton）
• SciPy：scipy.sparse.csgraph.dijkstra
• SciPy：scipy.sparse.csgraph.shortest_path

リンクと内容は2026年10月4日に確認しました。SciPy のドキュメントはバージョンによって変わることがあります。