IT資格用語解説応用情報技術者試験・代表的なアルゴリズム
ベルマンフォード法
更新日:
用語解説
ベルマンフォード法は、負の重みの辺があっても、出発点からすべての頂点への最短経路を求められる方法です。
■ 試験で押さえるポイント
すべての辺で距離の更新を、頂点の数−1回繰り返します。
重みの合計が負になる輪（負の閉路）があることも検出できます。
ダイクストラ法より計算に時間がかかります。
方法 | 負の重み | 計算量 | 特徴 |
|---|---|---|---|
ダイクストラ法 | 扱えない | O(E log V)（優先度付きキュー使用時） | 最も近い未確定の頂点を順に確定する |
ベルマンフォード法 | 扱える | O(V×E) | 全ての辺の緩和を V−1 回繰り返し、負の閉路も検出できる |
■ 過去問での着眼点
負の重みに対応できる点で、ダイクストラ法と区別します。
例: 割引などで費用が負になる経路を含む場合に、最も安い経路を求めます。