読み方：ベルマンフォードほう

ベルマンフォード法【Bellman–Ford algorithm】

概要

ベルマンフォード法とは、重み付きグラフにおいて、ある頂点から他のすべての頂点までの最短経路を求めるアルゴリズムの一つ。辺の重みに負の値が含まれていても正しく機能し、負の重みを持つ閉路の検出にも用いられる。道路網や通信ネットワークの経路制御など、複数の地点を結ぶ経路の中から最もコストの低い道筋を求める場面で利用される。

始点の距離を0、他の頂点の距離を無限大として初期化する。続いて、すべての辺について、始点からの距離を経由することでより短い経路が見つかるかどうかを確認し、見つかった場合はその頂点の距離を更新する。この操作は「緩和」と呼ばれる。

頂点数をVとすると、緩和処理はV-1回繰り返す。負の閉路が存在しない限り、最短経路は同じ頂点を二度通らない単純な経路として表せるため、経路に含まれる辺の本数は最大でもV-1本となる。この性質により、V-1回の緩和で全頂点の最短距離が確定する。さらにもう一度すべての辺を調べ、なお距離を短くできる辺があれば、その頂点から到達可能な範囲に負の閉路が存在すると判断できる。

同じく最短経路を求める手法に「ダイクストラ法」があるが、未処理の頂点のうち重みが最小のものを選んで緩和していく方式である点がベルマンフォード法と異なる。ダイクストラ法は辺の重みが負の値を含む場合に正しく動作しないのに対し、ベルマンフォード法は負の重みを含むグラフでも正しい最短距離を求められる。ただし、計算量は頂点数V、辺数Eに対して O（VE）となり、ダイクストラ法より処理に時間がかかるため、負の重みを扱わない場合はダイクストラ法の方が好まれる。

なお、「負の閉路」とは、一周すると辺の重みの合計が負になる閉路のことである。このような閉路を繰り返し通ることで経路の総コストを際限なく小さくできるため、通常の意味での最短経路は定まらない。ベルマンフォード法は、緩和処理を繰り返しても頂点の値が更新され続けるかどうかを調べることで、この異常な状態を検出できる。

この手法は1950年代にリチャード・ベルマン（Richard E. Bellman）とレスター・フォード・ジュニア（Lester R. Ford Jr.）がそれぞれ独立に考案し、後にその成果が組み合わされて現在の形になった。この考え方を応用した経路制御の方式は、RIP（Routing Information Protocol）など初期のルーティングプロトコルの基礎としても用いられており、各ルータが隣接する機器と経路情報を交換しながら目的地までの最小コストの経路を算出する仕組みに反映されている。

(2026.8.29更新)