非負辺重みとは何か？定義と直感、Dijkstra・Bellman–Ford・Johnsonで読み解く最短経路アルゴリズム
エバープレイ編集部非負辺重みとは何か — 定義と直感
「非負辺重み（ひふへんじゅうみ）」とは、グラフ理論において各辺に割り当てられた重み（コスト、距離、時間、利得の逆数など）が 0 以上（≥ 0）であることを意味します。すなわち、任意の辺 e に対して w(e) ≥ 0 が成り立つグラフを指します。多くの現実世界の問題（道の距離、所要時間、料金など）ではコストが負になることは原則ないため、非負辺重みの仮定は自然であり、アルゴリズム設計でも頻繁に利用されます。
なぜ「非負」が重要か — アルゴリズムへの影響
非負性は最短経路アルゴリズムの動作保証に直結します。代表的な点は次のとおりです。
- Dijkstra（ダイクストラ）法：全ての辺の重みが非負であることを前提に設計されています。Dijkstra は「最小距離の頂点を確定していく」貪欲法であり、辺重みが負だと一度確定した頂点の距離が後から短くなる可能性があるため正しく動作しません。
- Bellman–Ford（ベルマン・フォード）法：負の辺重みを含んだグラフにも対応でき、負のサイクルの検出が可能です。ただし計算量は O(VE) と Dijkstra に比べて遅くなります。
- Johnson のアルゴリズム：全点対最短経路を求める手法で、まず Bellman–Ford でポテンシャルを求め、辺の再重み付けにより非負化してから各頂点から Dijkstra を使うことで高速化します。
Dijkstra が非負を必要とする理由（直観と例示）
Dijkstra の核心は「現在取り出した（距離が最小の）頂点は最終的な最短距離が確定している」という不変条件です。これは辺コストが非負であるため、未処理の頂点を経由することで取り出した頂点の距離がさらに小さくなることがありえない、という性質に依存します。
反例を挙げます。頂点 s から x へ 1、x から y へ 1、s から y へ 4、そして x から z へ −3（負の辺）があるとします。Dijkstra は s→x（1）を確定し、次に y（現在距離 4）を取り出すかもしれませんが、x→z の負辺があると、z 経由で y の距離が後から改善される可能性があります（確定した y を後で更新できるようにする必要がある）。これにより Dijkstra の「確定は最終」ルールが破られ、誤った結果になります。
負の辺重みが許される場合の解法と特徴
- Bellman–Ford：単一始点最短路で負の辺を扱え、負の閉路を検出できる。計算量は O(VE)。グラフが疎（E が小さい）場合に実用的。
- SPFA（Shortest Path Faster Algorithm）：Bellman–Ford のキュー最適化版で、平均的に高速だが最悪ケースでは非常に遅くなる（負のサイクルが絡む場合など）。実装上の注意点が多い。
- Johnson：全点対最短路のために Bellman–Ford でポテンシャル h(v) を計算し、w'(u,v) = w(u,v) + h(u) − h(v) により非負化。これで各頂点から高速な Dijkstra を適用できる。
最小全域木（MST）と負の重み
MST（最小全域木）アルゴリズム（Kruskal、Prim）は辺の非負性を必要としません。MST の目的は辺の合計重みを最小化することであり、辺重みが負でも「最小」という概念はそのまま扱えます。負の辺があると、MST の総重みは負になり得ますが、アルゴリズムの正当性に影響はありません。これは MST が「重みの大小関係」だけを用いて辺を選択するためです。
現実問題でのモデリングの注意点
- コストが負になる意味を明確にする：負の値は「利益」や「回収」を表す場合があります。例えば通貨交換のアービトラージ検出では、変換率に −log を取ることで「負の閉路＝利益サイクル」を検出できます。
- 単純に定数を足して非負化してはいけない：全ての辺に定数 c を加えると、パス全体のコストは辺数に応じて変わるため、最短経路の順序が変わる可能性があります。任意のパス長が異なる問題に対しては無効です。
- 精度と型の選択：重みが大きい、または多数辺を経由する経路の合計でオーバーフローする可能性があるため、整数では 64-bit、実数では適切な infinity（無限大）管理や比較用のイプシロンを用いること。
実装上の注意点と最適化
- Dijkstra の実装：通常は優先度付きキューを使います。減少鍵（decrease-key）をサポートしない実装では、距離が更新されるたびに新しいエントリを push し、古いエントリを無視する手法が一般的です。
- 重みの型：整数重みの範囲が小さい場合、Dial のアルゴリズム（バケットベース）や 0-1 BFS（辺重みが 0 または 1 の場合）などの特殊化で高速化できます。実数重みには適さない。
- 浮動小数点：浮動小数点の誤差に注意。比較はイプシロンを使うか、問題に合わせて適切な型を選ぶ。
- 負のサイクル検出：Bellman–Ford の後にさらに緩和が可能なら負の閉路が存在する。これを検出して適切に扱う（報告、無限に短くなる、など）。
非負辺重みを前提にするアルゴリズム・応用例
- 経路探索（ナビゲーション、配送計画）：距離や所要時間は非負であるため Dijkstra がよく使われます。
- ヒューリスティック探索（A*）：ヒューリスティック関数は一貫性（consistency）または可許性（admissibility）が必要で、実際の移動コストが非負であることが前提の設計が多いです。
- ネットワーク設計や最短経路を繰り返す最適化（ラウト計画、交通シミュレーションなど）：大規模グラフでは Dijkstra の効率性が重要。
まとめ — いつ非負を仮定すべきか
非負辺重みの仮定は多くの実問題で自然であり、Dijkstra など高速なアルゴリズムを利用可能にします。しかし、問題ドメインで負の辺の意味があるなら（利益、回収、為替の対数変換など）、負の辺を許すアルゴリズム（Bellman–Ford、Johnson、SPFA など）を選ぶ必要があります。モデル化の段階で「負の値が何を表すか」「定数を加えて非負化できないか」「負の閉路が意味する現象（無限増益など）が存在しないか」を慎重に検討してください。
参考文献
- Dijkstra's algorithm — Wikipedia
- Bellman–Ford algorithm — Wikipedia
- Johnson's algorithm — Wikipedia
- Minimum spanning tree — Wikipedia
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms（教科書）
投稿者プロフィール
