ベルマンフォード法

ベルマンフォード法とはグラフにおける最短経路を求めるアルゴリズム(解法)の一つ.有効グラフの時に使える.この他にも最短経路を求めるアルゴリズムにはダイクストラ法やワーシャルフロイド法が存在する.
身近な例 : ある駅からある駅にいくのに複数の行き方があった時に最小の値段を計算する

特徴

負の経路を含んでいても使うことができる
ダイクストラ法よりは計算量が大きくなってしまう
計算量はO(|V||E|)

原理

イメージとしては,DP+全探索.すなわち配列の中身を徐々に更新していく.文字で言ってもさっぱりわからないからやはり図にしてみよう. 今回はこのグラフについて考える

A → E への最短経路を求める

f:id:topaz1-3:20190310233500p:plain — graph

A→Eへの行き方は複数通り考えることができる.その中で最小の行き方を求めたい.
まずはじめに初期化する

スタート地点を0
他の場所全てをINF(とても大きな数字)に設定する.

f:id:topaz1-3:20190310233927p:plain 次にINF以外の地点から伸びている経路の部分を更新する. f:id:topaz1-3:20190310234723p:plain A→Cの経路を用いてCにいくと4のコストを使っていけることがわかります.なのでCの地点をINFから4に更新します.同様にA→Bの経路についても見てみるとBの地点を1に更新することができます. f:id:topaz1-3:20190310234920p:plain 今度はB→Cの経路に注目してみます. f:id:topaz1-3:20190310235140p:plain

現時点でCは4になっていました.
Bからの道を通ると 1 (現在のB) + 2 (移動にかかるコスト) = 3

これらのうち小さい方を採用します.今回は3の方が小さくなります.よって3でC地点を更新します. f:id:topaz1-3:20190310235504p:plain 同じ更新作業を繰り返すと全ての地点へいく最低コストを求めることができます. f:id:topaz1-3:20190310235857p:plain

計算量

なぜ計算量がO(|V||E|)の辺の数と頂点の数の席になるのか.
まず毎回のループで全部の道を調べるのでE回になります.この時道のスタート地点がINFとなっている場合は道の行き先を更新していないだけでINFかどうかの確認をしています.
次にループを何回しているかです.結論は|V - 1|回すれば事足ります.上に示した例の最初をみて欲しいのですが最初のループでB地点が1,C地点が4になりました.C地点の4はあとで更新されますが,B地点の1というのは確定してこのあと更新されることはありません.1回目のループで一箇所(B地点)への最短経路が確定しました.このようにループを一回行うごとに一箇所以上の最短経路が確定する場所が出てきます.そのため初期位置以外の|V - 1|箇所のループを行えば確定することがわかります.(実際にはV - 1回以下で確定することもある)

参考

計算量