ベルマン・フォード法についてやっと理解したのでメモします。

今回はコードは書かずに具体例を用いて、その最短経路を求める手順を述べながら説明していこうと思います。

僕の理解力がないのがいけないのか、他のドキュメントは大事なことが抜けていることが多い。抜け目なく、理解できるように書いたので冗長になっているかと思いますが、ご許しを。それだけ難しいものだってことで笑

---

ベルマンフォード法

グラフ理論とかで登場する、グラフの2点間の最短経路を求めるアルゴリズムの一つ。ダイクストラ方とよく比較される。

ついでにダイクストラ法について知りたい方はこちら。

上の図で考えます。

手順

1. 出発点をa,目的地をfとします。さらに全ての点までの距離を到達可能不明という意味で「∞」と仮定します。
2. aから一回の移動（一辺の移動）でいけるところ（bとc）へ移動します。
3. とりあえずbとcの重み（距離）を更新します。（b=5, c=4）
4. bとcから1辺（1回の移動）でいけるところへ進む(b→c,d      c→d,e,f)
5. c,d,e,fの重みを更新

ここがベルマンフォード法で気をつけなければいけないところです。というよりここだけ気をつければベルマンフォード法は攻略したも同然です。

• 更新の際、b→c,d　とc→d,e,fは別のものとして考えます。つまり、b→cと重みを更新し、そのcを用いてd,e,fを更新してはいけない
• b→c で更新したcをC_bとするならば、a→Cで更新したC_aとは「別物」であるということが重要。
• あくまで更新作業をする際（更新計算を行う際）は「同じ手順で進んだもののみである」
• 手順5の場合、c→e(E_c)、b→c (C_b)、c→f(F_c)、b→d(D_b)が更新されることになる

そうすると{e = 5, c=3, f = 8, d = 6}となる。１回目の移動（手順3）で重みがすでに存在する場合、両者を比較し小さい方で更新する。

ここまでの重みの更新情報を図に示します。黄緑が一回目の更新での重み。青が二回目（手順5）で更新した重みです。

 

6. 手順5で更新したc,d,e,fから一辺でいけるところへ移動。

fは最終地点なのでこれ以上移動できません。dとeはfへ移動できます。cは先ほど同様d,e,fへ移動します。

7.手順6で移動した所の更新作業をします。

更新作業をした図は以下です。手順7での重み更新を赤文字と赤矢印で書いています。更新した重みはピンクで囲っています。

8.dとeから一辺でいけるfへ移動します。

9.手順7で更新した重みを用いて更新作業をします。

９でやってみるとわかりますが、すでに存在する7の方が小さくなるので、手順9では重みは更新されず、今回の問題（a→f）での最短距離は『7』で決定します。

決定した最短経路を示します。

このように全ての辺に注目し、重みが更新されなくなるまで繰り返す方法が「ベルマンフォード法」です。

ダイクストラ法より計算量が多いとも言えるような少ないとも言えるような微妙な部分ですが、辺の重みが「負」でも計算できるので汎用性という意味では、こちらの方が良さそうです。

 

今回はコーディングについては一切触れなかったので、次は理解したことをコードに落とし込んでいこうと思います。

スポンサードリンク