テクノロジ
ベルマンフォード法とは
読み方：ベルマンフォードほう
ひとことで言うと：負の辺を含むグラフでも最短距離を求め、負閉路も検出できるアルゴリズム。
意味をわかりやすく解説
ベルマンフォード法は、一つの始点から各頂点への最短距離を求めるアルゴリズムで、負の重みを持つ辺があっても利用できます。
すべての辺について緩和を頂点数-1回まで繰り返します。その後さらに距離が短くなる辺があれば、始点から到達可能な負閉路が存在すると判定できます。
具体例
頂点数5のグラフなら、全辺の緩和を最大4回繰り返して距離を伝播させます。
似た用語との違い
ダイクストラ法
ベルマンフォード法は負辺に対応し負閉路を検出できます。ダイクストラ法は負辺なしを前提に、より効率よく処理できます。
負閉路
一周すると総重みが負になる閉路があると、周回するたび距離を小さくできるため最短距離が定まりません。
覚え方
負の辺OK、全辺を何度も緩和。さらに更新できたら負閉路。
基本情報技術者試験の試験ポイント
V個の頂点ならV-1回の緩和、負閉路検出という特徴をダイクストラ法と比較します。
CHECK QUESTION
ベルマンフォード法でV-1回の緩和後、さらに距離が短くなる辺が見つかった場合、何が分かりますか。
答えを見る
始点から到達可能な負閉路が存在すると判断できます。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。