ベルマン・フォード法の対象試験と出題頻度
ダイクストラ法を覚えた直後にベルマン・フォード法が出てきて、違いが分からないまま止まってしまう。
最短経路の学習でよくある詰まり方です。応用情報技術者試験での立ち位置は明快で、午前の4択に1行の説明文として登場する型が主。
「負の重みを含むグラフでも最短距離を求められる」という一点を、ダイクストラ法の対概念として押さえれば、頻出度Dの用語としては十分に戦えます。
筆者も受験時は名前だけ覚えて捨てていました。
転機はネットワーク分野で、RIPの無限カウント問題を学んだとき。
「更新が止まらない」という現象が負閉路で終われない構造とそのまま重なり、分野をまたいで一気に腹落ちしました。頻出度Dでも、こうした結節点になる用語は覚えておく価値がある。
出題情報を確認する
応用情報技術者試験(AP) 基本情報技術者試験(FE・シラバス収録)
★☆☆☆☆
ランクD(シラバス収録語。ダイクストラ法の対概念として押さえる)
ベルマン・フォード法の定義
ベルマン・フォード法は、名前の重厚さに比べてやっていることが単純です。難しく感じる原因は、たいてい「緩和」という用語に集約されている。
1950年代にリチャード・ベルマンとレスター・フォードが独立に示した手法で、動的計画法の考え方をグラフの最短経路に当てはめたもの。アルゴリズムの学習では、ダイクストラ法とセットで扱われる位置にあります。
ベルマン・フォード法とは、
「負の重みがあっても始点から各点への最短距離を全辺の緩和反復で求める手法」
です。
ポイント還元付きの乗り換えを思い浮かべてみてください。「この路線を通ると300円もらえる」という区間があると、遠回りのほうが総額では安くなる。
すると「今いちばん安い駅から順に確定していけばよい」という発想そのものが崩れてしまいます。
📊 ベルマン・フォード法の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Bellman–Ford Algorithm |
| 解く問題 | 単一始点最短経路問題(1つの始点から全ノードへの最短距離) |
| 適用条件 | 辺の重みに負の値を含んでよい/負閉路がある場合は「解なし」を検出して終了 |
| 計算量 | O(V×E)(V=ノード数、E=辺の本数) |
| 提唱者 | リチャード・ベルマン、レスター・フォード |
| 実務例 | ディスタンスベクタ型ルーティング、割引・還元を含むコスト最小化、為替の裁定検出 |
ベルマン・フォード法の解説|緩和を繰り返すだけで最短距離が出る
手順は3ステップしかありません。
ダイクストラ法の「最小を選ぶ→確定→更新」と違い、選ぶ判断が一切ないところが構造上の分かれ目。
ベルマン・フォード法の計算手順(3ステップ)
dist[始点]=0
他は十分大きい値
確定させず
全ての辺を機械的に見る
更新が起きれば
負閉路あり=解なし
ノードを選ぶ工程がないぶん、負の重みでも手順が壊れない
緩和(relaxation)とは「遠回りしたら短くなったので書き換える」操作
緩和は、辺 (u, v) について dist[v] > dist[u] + 重み が成り立つとき、dist[v] を dist[u] + 重み に書き換えるだけの一手です。
「今の記録より、uを経由したほうが短い」という発見を反映する作業。この判定を全ての辺に対して順番に流すだけで、次に見るノードを選ぶ必要はありません。
なぜ |V|−1 回で足りるのか(最短経路が通る辺は最大 |V|−1 本)
最短経路が同じノードを2度通ることはないため、経路に含まれる辺は最大で |V|−1 本。
全辺を1周スキャンすれば、少なくとも1本ぶん先まで正しい距離が伝わるので、|V|−1 周あれば全ノードに届く計算になります。
負の辺 C→B(重み −4)を1本含む5ノードの有向グラフで、実際の遷移を追ってみてください。
📊 トレースに使う有向グラフ(始点A・負の辺は C→B の −4)
赤い C→B が負の辺。Aから直接行くとB=2だが、C経由なら 5−4=1 でさらに短くなる
緩和トレース表(始点A/上図の6本の辺を A→B、B→D、D→E、A→C、C→E、C→B の順に走査)
| 反復 | A | B | C | D | E | この周で起きたこと |
|---|---|---|---|---|---|---|
| 初期化 | 0 | ∞ | ∞ | ∞ | ∞ | 始点のみ0、他は十分大きい値 |
| 1回目 | 0 | 2 → 1 | 5 | 5 | 7 | 周の最後に C→B(−4) を見て、確定済みに見えたB=2を1へ書き換え |
| 2回目 | 0 | 1 | 5 | 4 | 6 | Bの修正がD・Eへ波及(5→4、7→6) |
| 3・4回目 | 0 | 1 | 5 | 4 | 6 | 更新なし。|V|−1=4回で最短距離が確定 |
| 5回目(判定) | 0 | 1 | 5 | 4 | 6 | 更新が起きない=負閉路なし |
トレース演習:同じグラフをダイクストラ法で解くとEはいくつになるか
答えは 7。最小値のB=2を先に確定させてしまい、あとから C→B(−4) でB=1に縮まっても反映できないため、正解の6にたどり着けません。1マスの書き換えが、そのまま両手法の適用条件の差になっている。
計算量 O(V×E) の導出(二重ループの外側と内側)
for i を 1 から |V|-1 まで ← 外側:|V|-1 回
for 各辺 (u, v, w) について ← 内側:辺 E 本
if dist[u] + w < dist[v]
dist[v] ← dist[u] + w ← 緩和
外側が |V|−1 回、内側が E 本。
掛け合わせて O(V×E) となります。オーダー記法では定数と下位項を無視するため、|V|−1 は V として扱う。
密なグラフでは E が V² に近づくので、ダイクストラ法の O(V²) より重くなる点が試験での比較軸になります。
📝 ポイント整理
・緩和=「経由したほうが短ければ書き換える」判定を全辺に流す操作
・最短経路の辺数は最大 |V|−1 本 → |V|−1 回の反復で十分
・二重ループの構造がそのまま O(V×E) に対応する
試験ではこう出る!ベルマン・フォード法の出題パターン
ベルマン・フォード法を直接の主題とした午前問題は、公開されている過去問では確認できていません。
本用語はAP・FEのシラバス(アルゴリズムとプログラミング/グラフのアルゴリズム)に収録された語であり、頻出度Dの根拠もそこにあります。
実際に出るのは最短経路問題そのもので、本手法は選択肢や適用条件の確認として顔を出す形。
出題パターン分析
📝 IPA試験での出題パターン
パターン1:用語識別型(本命)
4択の1行説明として「負の重みを含むグラフでも最短経路を求められる」が正誤判定される。ダイクストラ法の選択肢と並置されるのが典型。
パターン2:手法選択型
重みの符号と始点の数を条件として与え、適切な手法を選ばせる。ワーシャル・フロイド法との混同を誘う作りが多い。
パターン3:周辺知識型
午後の最短経路問題(AP 令和6年春 午後問3など)で、ダイクストラ法の適用条件を確認する文脈として登場する。
最短経路問題としての出題実績を確認する
AP 平成26年秋 午前 問5:グラフの頂点V1からV4・V5・V6への最短所要時間を求め、短い順に並べる(正解:イ)
AP 令和6年春 午後 問3(プログラミング):車載ナビを題材にノード間最短経路を求める。ダイクストラ法の擬似言語・トレース・計算量(記述式)
FE 平成29年春 午後 問8(データ構造及びアルゴリズム):副プログラム ShortestPath。最短距離を順次確定する実質ダイクストラ法(記述式)
上記3件はいずれも最短経路問題としての出題。ベルマン・フォード法そのものを主題とした午前問題は公開過去問では確認できていない。
ひっかけポイントと対策
選択肢の切り分けは、重みの符号と始点の数の2点で足ります。誤答の正体を先に覚えておけば即答できる。
⚠️ ひっかけ早見表
| 誤答の値・選択肢 | その正体 |
|---|---|
| 全ての頂点対の最短経路を求める | ワーシャル・フロイド法。単一始点ではない |
| 非負のグラフで短い順に確定 | ダイクストラ法。条件と手順の両方が違う |
| 重みなしで最少ホップ数を求める | 幅優先探索。重みの概念を持たない |
| 最も時間がかかる経路を求める | クリティカルパス。最長なので方向が逆 |
📝 試験区分別の対策方針
・AP:「負の重みOK/単一始点/O(V×E)/負閉路検出可」の4点セットで午前1点狙い
・FE:シラバス収録語。ダイクストラ法との対で名前と条件だけ押さえる
・IP/SG:出題対象外。深追い不要
負の重みで何が起きるのか|ダイクストラ法が使えない理由と負閉路の正体
ダイクストラ法が負の重みで破綻する原因は、手順そのものにあります。
最小の距離を持つノードを選んで確定させる構造なので、確定後に負の辺で距離が縮まっても、もう戻れない。前掲のトレース表でB=2が1に書き換わった一手が、まさに「確定を覆す」瞬間です。
確定して進むほうの手順はダイクストラ法の記事で確認してください。
一方の負閉路は、一周すると重みの合計が負になる閉路のこと。
回り続けるほど距離が下がるため、最短距離という答えそのものが存在しません。
|V|−1 回の反復後にもう1回緩和して更新が起きたら、「まだ下がる余地がある=負閉路あり」という判定になります。RIPの無限カウント問題も、更新が止まらないという同じ構造の別名。
実務では、物流の配送計画システムで「補助金や共同配送の割引で区間コストが実質マイナスになる」という要件に直面したことがあります。
既存のダイクストラ実装はそこで破綻。
距離を金額で持つ設計にすると符号は普通に反転するのだと、試験知識が設計判断に直結した瞬間でした。
手法の選び方は次の表で整理しておくと迷いません。
📊 最短経路の手法切り分け表(重みの符号と始点の数で選ぶ)
| 手法名 | 重みの条件 | 始点の数 | 負閉路検出 | 計算量 |
|---|---|---|---|---|
| 幅優先探索 | 重みなし(全て等価) | 単一始点 | 不可 | O(V+E) |
| ダイクストラ法 | 非負のみ | 単一始点 | 不可 | O(V²) |
| ベルマン・フォード法 | 負を含んでよい | 単一始点 | 可 | O(V×E) |
| ワーシャル・フロイド法 | 負を含んでよい(負閉路なし前提) | 全点対 | 対角成分で判定可 | O(V³) |
【確認テスト】ベルマン・フォード法の理解度チェック
Q. ベルマン・フォード法の説明として、最も適切なものはどれか。
- A. 辺の重みに負の値が含まれるグラフであっても、ある1つの始点から各ノードまでの最短距離を、全ての辺に対する緩和処理を繰り返すことで求める手法。
- B. 辺の重みが全て非負であるグラフにおいて、始点から最短距離が短いノードから順に距離を確定していく手法。
- C. グラフ上の全ての頂点の組合せについて、2頂点間の最短距離をまとめて求める手法。
正解と解説を見る
正解:A
解説:
「負の重みを含んでもよい」「単一始点」「全辺の緩和を反復」の3要素がそろっているかが選択肢を切る基準。この3点を含むのはAだけです。
Bが不正解の理由:ダイクストラ法の説明。非負限定という条件と「短い順に確定」という手順の両方が本手法と異なる。この1行を見た瞬間にダイクストラだと判定できる状態が目標。
Cが不正解の理由:ワーシャル・フロイド法の説明。全点対最短経路を求めるもので単一始点ではなく、計算量も O(V³) で異なる。
ベルマン・フォード法の関連用語ネットワーク
グラフの基礎から最適化・ルーティングまで、横に繋げておくと得点源が広がります。