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

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

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

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

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

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

なお、本文中の「グラフの辺の数を上限として繰り返し行われ」という表現は誤解されやすいため、ここでは 「頂点数Vに基づきV-1回」 と明確にします。緩和する対象は各回ごとに「全ての辺（E本）」であり、結果として全体計算量がO(VE)になります。

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

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

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

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

ダイクストラ法との違い

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

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

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

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

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

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

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

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

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

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

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

ここで重要なのは、「繰り返し回数の基準は辺数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) 程度で動作します。したがって、負の重みが存在しないことが確実なら、ダイクストラ法が選ばれることが多くなります。

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

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

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

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

初期化とエッジの処理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ベルマンフォード法を持ち込むなら、「制約付きの差分制約系（difference constraints）を最短路問題へ帰着する」という文脈で説明すると整合的です。単に「辺の重みをタスク時間にして最短完了時間」と言い切ると誤解を招きやすいため、本記事では「差分制約や制約充足のモデル化に関連する」程度に留め、過度な一般化は避けます。

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

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

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

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

まとめ

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