IT用語集 2024/11/21

ベルマンフォード法とは？ 10分でわかりやすく解説

Q: ベルマンフォード法は何を解くアルゴリズムですか？

重み付きグラフで、単一の始点から各頂点への最短距離（必要なら経路）を求めるアルゴリズムです。負の重みが含まれても、負閉路がなければ正しい結果を得られます。

Q: 負の重みがあるとダイクストラ法はなぜ使えませんか？

ダイクストラ法は「いったん確定した最短距離は、その後も短くならない」という前提で動きます。負の重みがあると確定済みの距離が後から更新され得るため、その前提が崩れて誤答につながります。

Q: ベルマンフォード法は負の重みがあっても正しく動きますか？

始点から到達可能な負閉路が存在しない限り、負の重みを含むグラフでも正しい最短距離を求められます。負閉路がある場合は「最短距離が定義できない」ことを検出できます。

Q: ベルマンフォード法の緩和（relaxation）とは何ですか？

辺(u, v, w)に対し、dist[u] + w が dist[v] より小さければ dist[v] を更新する操作です。これを全辺に対して繰り返し、最短距離の情報をグラフ全体に伝播させます。

Q: 緩和処理は何回繰り返しますか？

頂点数をVとすると、負閉路がなければ全辺の緩和をV-1回行うことで最短距離が確定します。繰り返し回数の基準は辺数Eではなく頂点数Vです。

Q: ベルマンフォード法の計算量はどの程度ですか？

全辺（E本）の緩和をV-1回行うため、計算量はO(VE)です。密なグラフではEがV^2に近づき、O(V^3)に近い負担になることがあります。

Q: 負の閉路はどのように検出しますか？

V-1回の緩和後に、もう一度だけ全辺を緩和します。それでも更新が起きるなら、始点から到達可能な負閉路が存在すると判断します（更新が起きた頂点が閉路上とは限りません）。

Q: 負の閉路があると何が問題になりますか？

閉路を周回することで距離をいくらでも小さくできるため、「これが最短」という値が定義できません。そのため通常はエラー扱いにして処理を打ち切ります。

Q: 負の閉路検出はグラフ全体が対象ですか？

始点から到達可能な範囲が対象です。到達不能な別連結成分に負閉路があっても、始点からの最短経路には影響しないため通常は検出対象外です。

Q: 実装で性能を改善する工夫はありますか？

各周回で一度も更新が起きなければ、それ以降も更新は起きないため早期終了できます。また、dist[u]が無限大の頂点からの緩和をスキップするなど、無駄な計算を減らす実装も有効です。

コラム

ベルマンフォード法は、重み付きグラフにおける「単一始点最短経路問題」を解く代表的なアルゴリズムです。負の重みを含む辺があっても適用でき、さらに「負の閉路（負閉路）」の検出まで行える点が特徴です。一方で、計算量は一般にダイクストラ法より大きく、グラフ規模によっては実用上の工夫（早期終了や対象範囲の限定）が必要になります。本記事では、ベルマンフォード法が何を保証し、どのような条件で使うべきかを押さえたうえで、アルゴリズムの流れ・実装の要点・代表的な応用例までを整理します。

ベルマンフォード法とは？

ベルマンフォード法（Bellman-Ford algorithm）は、重み付きグラフにおいて、ある始点（単一始点）から他のすべての頂点への最短距離を求めるアルゴリズムです。辺の重みが負であっても動作する点が重要で、さらに「始点から到達可能な負の閉路」が存在する場合は、最短距離が定義できないことを検出できます。

ベルマンフォード法の定義

ベルマンフォード法は、各頂点までの最短距離の候補を段階的に更新（緩和）していくことで解を求めます。負の閉路が存在しない限り、最短経路は同じ頂点を二度通らない単純路として表せるため、経路に含まれる辺の本数は最大でも V-1本（Vは頂点数）です。ベルマンフォード法はこの性質を利用し、全辺の緩和処理を V-1回 繰り返すことで、最短距離を確定させます。

なお、繰り返し回数は辺数Eではなく、頂点数Vに基づいて 「V-1回」 と決まります。各回で緩和する対象は 全ての辺（E本） であり、結果として全体の計算量はO(VE)になります。

ベルマンフォード法の特徴

ベルマンフォード法の特徴は大きく二つあります。

負の重みを持つ辺を扱える：ダイクストラ法は負の重みがあると正しく動作しない一方、ベルマンフォード法は負の重みを含んでも正しい最短距離を求められます。
負の閉路を検出できる：始点から到達可能な負の閉路が存在する場合、閉路を周回することで距離を際限なく小さくできるため「最短」が定義できません。ベルマンフォード法はこの状況を検知できます。

一方で、計算量はO(VE)と大きくなりやすく、頂点数・辺数が大きいグラフでは実行時間が課題になります。

ダイクストラ法との違い

ベルマンフォード法とダイクストラ法は、いずれも単一始点最短経路問題を解きますが、前提条件と得意領域が異なります。

ベルマンフォード法：負の重みを含んでも良い。負の閉路検出が可能。一般に計算量は大きい。
ダイクストラ法：負の重みがないことが前提。優先度付きキューを用いることで高速化しやすい。負の閉路検出は目的ではない。

設計・実装の現場では、「負の重みがあり得るか」「負の閉路の検知が必要か」「規模と性能要件はどうか」を軸にアルゴリズムを選びます。

アルゴリズム	負の重み	負の閉路検出	代表的な計算量
ベルマンフォード法	可	可（始点から到達可能な範囲）	O(VE)
ダイクストラ法	不可	不可	O((V+E)logV)

ベルマンフォード法が解決する問題

ベルマンフォード法は、次のような課題で使われます。

単一始点最短経路問題：始点から各頂点への最短距離（必要なら経路）を求める。
負の閉路検出：始点から到達可能な負の閉路が存在するかを判定する。
裁定取引（アービトラージ）の検出：為替レートを変換して負閉路検出に帰着させ、理論上の裁定機会を検知する。

最短経路はネットワーク設計やシステム最適化など幅広い領域で現れるため、ベルマンフォード法の「負の重みへの対応」「負閉路の検知」という性質を理解しておくと、アルゴリズム選定の判断がしやすくなります。

ベルマンフォード法のアルゴリズム

ベルマンフォード法の基本的な流れ

ベルマンフォード法の骨格は「初期化 → 全辺の緩和をV-1回 → 追加の緩和で負閉路検出」です。

距離配列distを初期化する（始点は0、それ以外は無限大）。必要なら直前頂点を記録するprevも用意する。
V-1回、全ての辺に対して緩和（relaxation）を行う。
もう一度だけ全ての辺を緩和し、更新が起きるかで負の閉路を判定する。

ここで重要なのは、「繰り返し回数の基準は辺数Eではなく頂点数V」である点です。最短距離が確定するために必要な上限が「V-1回」になる、という構造を押さえると誤解しにくくなります。

relaxation（緩和）の概念

緩和（relaxation）とは、ある辺(u, v, w)（uからvへ、重みw）を使ったときに、vへの最短距離の候補をより小さくできるかを確認し、できるなら更新する操作です。

もし dist[u] + w < dist[v] なら、dist[v]をdist[u] + wに更新し、必要ならprev[v] = uとする。

この操作を全辺に対して繰り返すことで、最短距離の情報がグラフ全体へ伝播していきます。負の重みがある場合でも、「今より短くできるなら更新する」という局所的な更新を積み上げることで正しい答えへ到達します。

負の閉路の検出方法

負の閉路（負閉路）とは、閉路上の辺重みの総和が負になる閉路です。負閉路が始点から到達可能な位置にあると、閉路を何周でも回って距離を無限に小さくできるため、最短距離は定義できません。

検出は次の考え方で行います。

V-1回の緩和が終わったあとに、もう一度全辺を緩和してみる。
それでもなお dist が更新できる辺が存在するなら、始点から到達可能な負閉路が存在すると判断する。

なお、「更新された頂点が負閉路上に存在する」と断定するのは強すぎます。更新が起きるのは、負閉路そのものの頂点に限らず、負閉路の影響を受ける（負閉路から到達可能な）頂点も含み得ます。実装上は「負閉路が存在する」と扱って処理を打ち切るか、必要なら閉路を復元する手順を追加します。

ベルマンフォード法の計算量と実装

ベルマンフォード法の計算量

ベルマンフォード法は、全辺の緩和をV-1回行うため、計算量は O(VE) です（Vは頂点数、Eは辺数）。密なグラフ（EがV^2に近い）ではO(V^3)に近づきやすく、規模が大きいと負担になります。

一方、ダイクストラ法は負の重みがないことを前提に、優先度付きキューを用いることで一般に O((V+E)logV) 程度で動作します。したがって、負の重みが存在しないことが確実なら、ダイクストラ法が選ばれることが多くなります。

ベルマンフォード法の実装方法

実装の基本は次の通りです。

グラフを「辺のリスト（u, v, wの配列）」として保持する（ベルマンフォード法は全辺走査が基本のため相性がよい）。
距離配列distと、経路復元用のprevを用意する。
distを初期化し、V-1回の緩和ループを回す。
追加の1回で負閉路の有無を判定する。

実用上は「ある周回で一度も更新が起きなかったらそこで打ち切る（早期終了）」を入れることで、平均的な実行時間を抑えられます。

初期化とエッジの処理

初期化では、始点のdistを0に、それ以外を無限大（十分大きい値）にします。無限大の扱いを誤ると、dist[u]が無限大のまま計算してオーバーフローする、といった不具合が起きやすいため、実装では「dist[u]が無限大なら緩和をスキップする」といった条件分岐が重要です。

エッジ処理（緩和）は、全辺を走査し、dist[u] + wでdist[v]が更新できるかを確認します。prevを更新する場合は、経路復元が必要なときに限り保持し、不要なら持たない（メモリと実装を簡素化する）判断も現場では一般的です。

負の閉路の検出とエラー処理

負閉路が存在する場合、最短距離は定義できません。そのため、実装としては「負閉路が検出されたら例外・エラーとして返す」「結果にフラグを立てる」などの扱いが必要です。

また、負閉路の検出は「始点から到達可能な範囲」に限られます。始点から到達できない別成分に負閉路があっても、始点最短経路問題の結果には影響しないため、検出対象外となります。この点は仕様として明文化しておくと誤解を防げます。

ベルマンフォード法の応用例

通貨の裁定取引（アービトラージ）への応用

ベルマンフォード法は、裁定取引（アービトラージ）機会の検出として紹介されることがあります。典型的には、為替レートをそのまま「重み」にするのではなく、積（レートの掛け合わせ）を足し算へ変換するために対数変換（例：-log(rate)）を用い、負閉路の有無を調べる形で「理論上の裁定機会」を検出します。

ただし、実際の金融取引では手数料・スプレッド・約定遅延などが大きく影響するため、アルゴリズム上の裁定機会がそのまま利益に直結するとは限りません。応用例として挙げる場合は、「理論モデルとしての検出」である旨を添えると誤解が減ります。

通信ネットワークにおける経路探索

通信ネットワークでは、ノード間の経路選択（ルーティング）を最適化したい場面があります。辺の重みを遅延・コスト・混雑度などとしてモデル化し、最短経路を求めることで、ある指標に基づいた「より良い経路」を探索できます。

一方で、現実のネットワーク運用では、単純な最短経路だけでなく冗長化やポリシー制御、動的なリンク状態、収束時間といった要件が絡みます。ベルマンフォード法は「モデル化できる範囲では有効だが、運用要件に合わせた仕組みが上乗せされる」という前提を添えると説明がブレにくくなります。

スケジューリング問題への応用

プロジェクト管理ではタスク依存関係を扱いますが、ここは補足が必要です。タスクの依存関係（先行・後続）と所要時間から「最短完了時間」を求める典型手法は、一般に最短経路というより「クリティカルパス（最長経路）」やDAG上の動的計画法として説明されることが多い領域です。

ベルマンフォード法を関連づけるなら、「差分制約（difference constraints）を最短路問題へ帰着する」という文脈で説明するのが整合的です。本記事では「差分制約や制約充足のモデル化に関連する」程度に留め、過度な一般化は避けます。

システム開発における活用シーン

システム開発では、コストやペナルティを含む経路探索、制約条件を含む最適化、依存関係の矛盾検出などが「グラフ」として表現できることがあります。たとえば、次のような形です。

制約の矛盾検出：差分制約を辺として表し、負閉路が矛盾を意味するケース（仕様上の整合性チェック）。
コスト最小化：経路に「割引（負のコスト）」が入るモデルでは、ダイクストラ法が使えず、ベルマンフォード法の対象になります。

ただし、実装上は「本当に負の重みが必要か」「負の閉路が起き得る設計になっていないか」を先に検討し、負の重みを避けられるなら避ける、という判断も重要です。負閉路は仕様上の矛盾や想定外の組み合わせを示すことが多く、アルゴリズム選定だけでなく、要件・データ設計の観点で扱うべき場合があります。

まとめ

ベルマンフォード法は、重み付きグラフにおける単一始点最短経路を求めるアルゴリズムで、負の重みを含む場合にも適用でき、さらに始点から到達可能な負の閉路を検出できる点が強みです。計算量はO(VE)で、規模が大きいグラフではダイクストラ法より不利になりやすい一方、仕様上「負の重みがあり得る」「負閉路検出が必要」といった条件では有力な選択肢になります。要点は、V-1回の全辺緩和と、追加の緩和による負閉路判定です。応用例としては、（理論モデルとしての）裁定機会検出や、制約の矛盾検出などがあり、現場では前提条件とデータ設計を含めて使いどころを見極めることが重要です。