ベルマン・フォード法


ここでは、探索アルゴリズムの1つであるベルマン・フォード法について解説します。

ベルマン・フォード法は、木構造やグラフ構造において、他のノードとの最短経路を探すためのアルゴリズムです。
その名前は開発者のリチャード・アーネスト・ベルマンとレスター・ランドルフ・フォードJrに由来しています。
ダイクストラ法とは異なり、コストに負数が含まれていても適用する事ができ、総和が負数の閉路がある場合には
使用できませんが、総和が負数の閉路を検知する事ができます。
ここで言うところのコストとは、隣接ノードへの行き辛さの事です。現実世界に当てはめて考えれば、
距離であったり、地形の良し悪しがコストとして考えられるでしょう。
例えば、コストを考慮したグラフというのは以下のようになります。

    
  ┏━┻━┓
 2┃   ┃3
  ┗━┳━┛
    

これはノード間のリンクに対してコストを記述している例となります。
,ら△愡蠅襯襦璽箸2つあり、左のルートであればコスト2で△惺圓韻泙垢、
右のルートであればコスト3かかってしまいます。
仮にコストを距離として捉えるならば、左のルートで行ったほうが近いという事です。

では、ベルマン・フォード法についてもう少し具体的に解説します。
ベルマン・フォード法は開始地点からあるノードへ至るまでの総コストを管理し、
全リンクのコストとの比較を、総コストの更新がなくなるまで繰り返す事で最短距離を
求めます。
総コストの更新の条件は、

あるノードへの総コストをV
あるノードの隣接ノードへの総コストをU
あるノードの隣接ノードからあるノードへのコストをC

とすると、「V>U+C」の場合に、VをU+Cで更新します。
これはどういう事かと言えば、あるノードへ至る既知の総コストより、別の隣接ノードを
経由した方が良い場合に総コストを更新するという事です。
この更新作業を総コストの更新が起きなくなるまで繰り返します。

例えば、以下の例を見てください。

    5     2
  ┏━━━━※━━━┓
 ;         ┣
  ┗━━━━━え━┛
   2   2   2

リンクに書いてあるマル無しの番号がコストです。
このグラフで,らイ悗虜巴桟佻を求める事を考えて見ます。

1.まず、開始地点,らの総コストを以下のように初期化します。
  {0, ∞, ∞, ∞, ∞}

2.△離痢璽匹砲弔い董
  「△領拈椒痢璽畢,料蹈灰好0」+「、△悗離灰好5」<∞
  なので、,ら△料蹈灰好箸鮃洪靴靴泙后
  {0, 5, ∞, ∞, ∞}

3.のノードについて、
  「の隣接ノード,料蹈灰好0」+「、へのコスト2」<∞
  なので、,らの総コストを更新します。
  {0, 5, 2, ∞, ∞}

4.い離痢璽匹砲弔い董
  「い領拈椒痢璽畢の総コスト2」+「→い悗離灰好2」<∞
  なので、,らい料蹈灰好箸鮃洪靴靴泙后
  {0, 5, 2, 4, ∞}

5.イ離痢璽匹砲弔い董
  「イ領拈椒痢璽畢△料蹈灰好5」+「□イ悗離灰好2」<∞
  なので、,らイ料蹈灰好箸鮃洪靴靴泙后
  {0, 5, 2, 4, 7}

  「イ領拈椒痢璽畢い料蹈灰好4」+「あイ悗離灰好2」<7
  なので、,らイ料蹈灰好箸鮃洪靴靴泙后
  {0, 5, 2, 4, 6}

もう更新は起きないので終わり。

これがベルマン・フォード法の動きとなります。
上記の例ではグラフが良くないので、総コストが一周で求まりますが、上記のような更新操作を
総コストの更新が起きなくなるまで繰り返します。

さて、上記の動きをアルゴリズムとしてまとめると以下のようになります。

前提:
   〜蹈灰好箸魎浜する配列の値を始点は0、他は非常に大きな値で初期化する
    (仮に総コストの配列をDistanceとする)
   ▲哀薀佞離螢鵐情報としてコスト、両端のノードの情報を持つデータ構造
    Link{
     コスト,
     ノードA,
     ノードB
    };
    を格納したコンテナLinksがある

1.更新フラグをfalseにする
2.Linksから1つリンク情報を取り出す。(仮に取り出したリンク情報をeとする)
3.もし、「Distance[e.ノードB]>Distance[e.ノードA]+e.コスト」ならば、
  Distance[e.ノードB]をDistance[e.ノードA]+e.コストで更新し、更新をtrueにする
4.Linksから全てのリンクを取り出すまで、「2.」から繰り返す
5.もし、更新フラグがtrueの場合は「1.」から繰り返す
  そうでなければ終了

これがベルマン・フォード法のアルゴリズムになります。
さて、基本的には上記のアルゴリズムでできますが、総和が負数の閉路を含む場合には上手く行きません。
閉路というのは、グラフ上における輪になっているような部分です。
その総和が負数となるような閉路を含むグラフとは例えば、以下のようなものです。

   3   2   3
 ;━━※━━え━━
     ┃   ┃
   −2┃   ┃−4
     ┃   ┃
     ━━━
       3

上記のグラフでは、□あア→△箸いΔ茲Δ坊佻を辿ると、コストの総和は「-1」となります。
するとどうでしょうか。仮に,らΔ悗虜巴桟佻を求めようと思った際に、この□あア→△
部分をぐるぐる回れば回る程総コストを減らす事ができてしまいます。
これでは総コストが定まりません。
従って、総コストが負数になるような閉路が存在する場合には使用できないという訳です。
しかし、ベルマン・フォード法では、総コストが負数になるような閉路がある場合には、最短経路を割り出す事は
できませんが、検知する事はできます。
というのも、上記で行ったアルゴリズムの説明で更新が起きなくなるまで繰り返すと説明しましたが、
この繰り返し作業はせいぜい「ノード数-1」回しか起きません。
つまり、それ以上ループを周り続けていれば総コストが負数になるような閉路があるという事になります。

さて、サンプルプログラムを提示しますが、サンプルプログラムではグラフを以下のような形で表現しています。

┏━━━━━━┓
┃SキΝ´ ┃
┃Ν   ┃
┃    ┃
┃ キ  ┃
┃  キ ┃
┃ Л G┃
┗━━━━━━┛

「S」がスタート地点であり、「G」がゴール地点です。
マスに書かれた番号がそのマスを通過する上での必要コスト、空白のマスはコスト無しで通過できます。
スタート地点からゴール地点に向かうにあたり、最小コストで行けるルートを求めます。
わざわざ空白のマスを用意しているのは、その方がぐにゃぐにゃ動いて見栄えが良いからです。
上記の結果は以下のようになります。

┏━━━━━━┓
┃S*Ν´ ┃
┃*Α**┃
┃─***┃
┃ キ *┃
┃  キ ┃
┃ Л G┃
┗━━━━━━┛

「*」が通過した経路で、「S」から「G」へ行くためのコストは「11」です。

では、サンプルプログラムを見て下さい。


#include <iostream>
#include <ctime>
#include <iomanip>

//プロトタイプ宣言
//グラフ生成関数
void CreateGraph(unsigned int*,unsigned int,unsigned int);
//グラフ描画関数
void PrintGraph(unsigned int*,unsigned int,unsigned int);
//ベルマン・フォード法アルゴリズム
void BellmanFord(unsigned int*,unsigned int,unsigned int,unsigned int,unsigned int);

const unsigned int INFINITY=0xFFFF;
//コスト用定数
const unsigned int COST_MAX=0x0A;
const unsigned int UP=0x0100;
const unsigned int RIGHT=0x0200;
const unsigned int DOWN=0x0400;
const unsigned int LEFT=0x0800;
const unsigned int START=0x1000;
const unsigned int GOAL=0x2000;
const unsigned int WALK=0x4000;

//総コスト用
unsigned int total_cost;

int main(void){
        std::srand(std::time(nullptr));

        //グラフ横幅・縦幅
        const unsigned int width=25;
        const unsigned int height=25;

        //グラフ用領域の確保
        unsigned int* graph=new unsigned int[width*height];
        //初期化
        std::fill(graph,graph+width*height,0);

        //グラフの生成
        CreateGraph(graph,width,height);

        //グラフの描画ベルマン・フォード法適用前
        PrintGraph(graph,width,height);

        //ベルマン・フォード法によりグラフに経路を設定
        BellmanFord(graph,width+1,(height-1)*width-2,width,height);

        //グラフの描画ベルマン・フォード法適用後
        PrintGraph(graph,width,height);
        
        //コスト合計出力(ゴールの総コスト)
        std::cout<<"Total Cost : "<<total_cost<<std::endl;

        //グラフ用領域の解放
        delete[] graph;

        return 0;
}

//ベルマン・フォード法関数
//graph:探索対象グラフへのポインタ
//start:スタート地点の添え字
//goal:ゴール地点の添え字
//width:グラフの横幅
//height:グラフの縦幅
void BellmanFord(unsigned int* graph,unsigned int start,unsigned int goal,unsigned int width,unsigned int height){
        //ノード数(外周除く要素数)
        unsigned int node_quantity=(width-2)*(height-2);
        //コスト用隣接行列領域
        unsigned int* costs=new unsigned int[node_quantity*node_quantity];
        //初期化(グラフからコスト管理用隣接行列を生成)
        for(unsigned int i=0;i<node_quantity;i++){
                for(unsigned int j=0;j<node_quantity;j++){
                        if(i==j)
                                costs[i+j*node_quantity]=0;
                        //隣接ノードのコスト設定
                        //上
                        else if(i==j-(width-2))
                                costs[i+j*node_quantity]=graph[i%(width-2)+i/(width-2)*width+width+1];
                        //右
                        else if(i==j+1 && j%(width-2)!=width-3)
                                costs[i+j*node_quantity]=graph[i%(width-2)+i/(width-2)*width+width+1];
                        //下
                        else if(i==j+(width-2))
                                costs[i+j*node_quantity]=graph[i%(width-2)+i/(width-2)*width+width+1];
                        //左
                        else if(i==j-1 && j%(width-2)!=0) 
                                costs[i+j*node_quantity]=graph[i%(width-2)+i/(width-2)*width+width+1];
                        //繋がってない
                        else
                                costs[i+j*node_quantity]=INFINITY;
                }
        }

        //始点・終点のグラフ座標を補正
        //(引数のグラフ用配列は外周があり、隣接行列の添え字と合わないため)
        unsigned int start_index=start-(width-1)-2*(start/width);
        unsigned int goal_index=goal-(width-1)-2*(goal/width);
        
        //始点からの最短距離格納用配列を生成
        unsigned int* distance=new unsigned int[node_quantity];
        //経路用配列を生成(path[i]にはiの前のノードの値を入れる)
        unsigned int* path=new unsigned int[node_quantity];

        //上記2つの配列を初期化
        for(unsigned int i=0;i<node_quantity;i++){
                unsigned int cost=costs[start_index*node_quantity+i];
                //最短距離格納用配列は隣接行列の始点行で初期化
                distance[i]=cost;
                //経路用配列は始点の隣接ノードの前のノードに始点を設定するように初期化
                if(cost!=INFINITY)
                        path[i]=start_index;
        }

        //探索処理
        bool update;
        //unsigned int count=0;
        do{
                update=false;
                
                //if((count++)==node_quantity){
                //        負数の閉路がある
                //        このプログラムではグラフに負数が無いのでコメントアウト
                //}

                for(unsigned int i=0;i<node_quantity;i++){
                        for(unsigned int j=0;j<node_quantity;j++){
                                //(始点→j)より、(始点→i)+(i→j)の方がコストが低い場合に更新
                                if(distance[j]>distance[i]+costs[i*node_quantity+j]){
                                        distance[j]=distance[i]+costs[i*node_quantity+j];
                                        update=true;

                                        //i→jのコストで更新したので、jの前のノードとしてiを設定
                                        path[j]=i;
                                }
                        }
                }
        }while(update);

        //経路設定
        unsigned int i=path[goal_index];
        unsigned int j=start_index;
        while(i!=j){
                graph[i%(width-2)+i/(width-2)*width+width+1]=WALK;
                i=path[i];
        }
        total_cost=distance[goal_index]-GOAL;

        delete[] costs;
        delete[] path;
        delete[] distance;
}

//グラフ生成関数の実装
//graph:グラフ用配列のポインタ
//width:グラフ横幅(4以上)
//height:グラフ縦幅(4以上)
void CreateGraph(unsigned int* graph,unsigned int width,unsigned int height){
        //4以上でなければ生成禁止
        if(width<4 || height<4){
                return;
        }

        //--------------
        //外周の設定
        //--------------

        //上下両端
        for(unsigned int x=1;x<width-1;x++){
                graph[x]=RIGHT|LEFT;
                graph[(height-1)*width+x]=LEFT|RIGHT;
        }
        //左右両端
        for(unsigned int y=1;y<height-1;y++){
                graph[y*width]=UP|DOWN;
                graph[(y+1)*width-1]=UP|DOWN;
        }
        //四隅
        graph[0]=RIGHT|DOWN;
        graph[width-1]=DOWN|LEFT;
        graph[(height-1)*width]=UP|RIGHT;
        graph[width*height-1]=LEFT|UP;
        //始点(左上)・終点(右下)
        graph[width+1]=START;
        graph[(height-1)*width-2]=GOAL;

        //--------------------
        //コスト付け処理
        //--------------------

        for(unsigned int y=1;y<height-1;y++){
                for(unsigned int x=1;x<width-1;x++){
                        if(graph[x+width*y]!=START && graph[x+width*y]!=GOAL)
                                //2分の1の確立でコストなしノード
                                if(rand()%2==0)
                                        graph[x+width*y]=0;
                                else
                                        graph[x+width*y]=rand()%COST_MAX+1;
                }
        }
}

//グラフ描画関数の実装
//graph:グラフ用配列のポインタ
//width:グラフ横幅
//height:グラフ縦幅
void PrintGraph(unsigned int* graph,unsigned int width, unsigned int height){
        for(unsigned int y=0;y<height;y++){
                for(unsigned int x=0;x<width;x++){
                        switch(graph[y*width+x]){
                                //グラフコスト(10まで)
                                case 0:
                                        std::cout<<"  ";
                                        break;
                                case 1:
                                        std::cout<<"";
                                        break;
                                case 2:
                                        std::cout<<"";
                                        break;
                                case 3:
                                        std::cout<<"";
                                        break;
                                case 4:
                                        std::cout<<"";
                                        break;
                                case 5:
                                        std::cout<<"";
                                        break;
                                case 6:
                                        std::cout<<"";
                                        break;
                                case 7:
                                        std::cout<<"";
                                        break;
                                case 8:
                                        std::cout<<"";
                                        break;
                                case 9:
                                        std::cout<<"";
                                        break;
                                case 10:
                                        std::cout<<"";
                                        break;
                                //上下壁
                                case UP:case DOWN:case UP|DOWN:
                                        std::cout<<"┃";
                                        break;
                                //左右壁
                                case LEFT:case RIGHT:case LEFT|RIGHT:
                                        std::cout<<"━";
                                        break;
                                //上右壁
                                case UP|RIGHT:
                                        std::cout<<"┗";
                                        break;
                                //上左壁
                                case UP|LEFT:
                                        std::cout<<"┛";
                                        break;
                                //下右壁
                                case DOWN|RIGHT:
                                        std::cout<<"┏";
                                        break;
                                //下左壁
                                case DOWN|LEFT:
                                        std::cout<<"┓";
                                        break;
                                //上右下壁
                                case UP|RIGHT|DOWN:
                                        std::cout<<"┣";
                                        break;
                                //右下左壁
                                case RIGHT|DOWN|LEFT:
                                        std::cout<<"┳";
                                        break;
                                //下左上壁
                                case DOWN|LEFT|UP:
                                        std::cout<<"┫";
                                        break;
                                //左上右壁
                                case LEFT|UP|RIGHT:
                                        std::cout<<"┻";
                                        break;
                                //十字壁
                                case UP|RIGHT|DOWN|LEFT:
                                        std::cout<<"╋";
                                        break;
                                case START:
                                        std::cout<<"S";
                                        break;
                                case GOAL:
                                        std::cout<<"G";
                                        break;
                                case WALK:
                                        std::cout<<"*";
                                        break;
                        }
                }
                std::cout<<std::endl;
        }
}



このプログラムの実行結果は以下のようになります。

┏━━━━━━━━━━━━━━━━━━━━━━━┓
┃S ´┃     ┃  き ┃
┃キ        キ       ┃
┃              Νキ Θ
┃ ┃       きき   ┃
┃   Ν          ┃
┃       Л┃ き  ┃
┃    ´´Ν     ↓┃Л  ┃
┃           ↓  き※
┃  キ┃Ν        Л ┃
┃    キ       ┃    ┃
┃     き キ↓き´´      ┃
┃  ЛΝ     き   Л´┬
┃      き    ´キ´Θ
┃   き           ┃
┃       Νき↓ キ      ┃
┃ キ    Ν↓キ↓ ↓   ┃
┃   ┃   ´   ┃   Θ
┃Лキ   ´  キ ┃´ エ
┃   キ       Ν   ┃
┃    き          ┃
┃  ↓↓    き     き ┃
┃           ´↓  ┃
┃   ´       ┃    G┃
┗━━━━━━━━━━━━━━━━━━━━━━━┛
┏━━━━━━━━━━━━━━━━━━━━━━━┓
┃S**´┃     ┃  き ┃
┃キ*       キ       ┃
┃**            Νキ Θ
┃ ┃       きき   ┃
┃ぁ* Ν          ┃
┃ぁ◆**   Л┃ き  ┃
┃  *ァ Ν     ↓┃Л  ┃
┃ ァ**Α***   ↓  き※
┃  キ┃Ν  ─     Л ┃
┃    キ *     ┃    ┃
┃     きАキ↓き´´      ┃
┃  ЛΝ  **  き   Л´┬
┃      き**** ´キ´Θ
┃   き     А***   ┃
┃       Νき↓ キ ぁ    ┃
┃ キ    Ν↓キ↓ *   ┃
┃   ┃   ´ **┃   Θ
┃Лキ   ´ ─キ ┃´ エ
┃   キ      **Ν   ┃
┃    き    ***** ┃
┃  ↓↓    き    *き ┃
┃              ┃
┃   ´       ┃  **G┃
┗━━━━━━━━━━━━━━━━━━━━━━━┛
Total Cost : 19

それでは解説します。

まず、グラフ生成用の関数であるCreateGraph関数及び、PrintGraph関数や定数は実質的には関係ありません。
これらは探索するためのデータを作成したり出力するための関数です。
ベルマン・フォード法によるアルゴリズムの実装であるBellmanFord関数です。

まず、使用しているグラフについて説明します。
探索対象となるグラフの盤面は配列で表します。
ベルマン・フォード法ではコストが分かれば良いので、コストを入れるため符号なしint型配列で表しています。
なお、コストとして扱うのは、10以下の値を入れたときのみです。
それ以上の値が入っている場合には、描画用の情報として扱います。詳しくは、プログラムの冒頭あたりに
定義されている定数群とPrintGraph関数のswitch文の分岐を見れば分かると思います。

続いて、BellmanFord関数ですが、引数としてグラフの配列graph、スタート地点の添え字start、
ゴール地点の添え字goal、グラフの幅width、及び高さheightを取るようにしています。
さて、BellmanFord関数でベルマン・フォード法の肝となっているのはdo-while文のところだけなのですが、
グラフのデータ構造がベルマン・フォード法では扱い辛いので、ベルマン・フォード法で扱いやすいようにしています。
グラフのデータ構造は単なるコストを格納しただけの配列ですが、描画用の情報まで一緒くたにしているので、
良くありません。また、リンクの情報が無く、コストはノードの値として持っているというのも良くありません。
このプログラムで使用しているグラフにリンクを追加して表現するなら以下のようになるでしょう。

    →
     
    ←
 ↓ ↑ ↓ ↑
    →
     
    ←

このように、各マスに双方向にリンクを張ったグラフとして置き換えれば、リンクのあるグラフとして見立てる事ができます。
そこで、BellmanFord関数では引数として与えられたグラフ情報から、リンクがあるグラフとして解釈できるように
隣接行列を生成する処理を入れています。
それが、関数冒頭の二重forループです。これにより変数costsに隣接行列を生成します。
この処理で、「costs[i*ノード総数+j]」により、iノード→jノードへのコストを得られるような隣接行列が作っています。
なお、隣接していない場合にはINFINITYという適当に大きい値を入れています。
隣接行列ができれば、後はアルゴリズムを適用するだけなのですが、まだ面倒な事があります。
引数のstart、goal変数はgraph配列上の添え字なのですが、graph配列は描画用の外周の壁も含んでいるため、
隣接行列の添え字としてはそのまま使えません。
そこで、隣接行列上の添え字と合うようにしなければなりません。
それがstart_indexとgoal_indexです。
ここまで来れば後は必要な変数を初期化してアルゴリズムを適用するだけです。
必要なものは総コストを保存するための配列であるdistanceです。ただ、ここでは経路も復元したいので経路復元用の
配列pathも用意しています。
初期値は、distance配列はスタート地点の隣接行列行と同じです。
「総コストを管理する配列の値を始点は0、他は非常に大きな値で初期化する」という説明をしましたが、
別に開始地点の隣接ノード値も総コストとして初期化していても変わりません。
path配列には開始ノードに隣接しているノードの前ノードとして開始ノードを設定しています。
後は、ベルマン・フォード法の肝となるdo-while文です。
最初に説明したアルゴリズムとは異なり、リンクの情報を隣接行列で処理しているため、分かり辛いかも知れませんが、
実質的には同じことです。リンク情報としてデータ構造を用意していれば、do-while文の中は一重ループだけで済みます。
なお、path配列の更新はコメントに書いてある通り、更新時に経由するノードの値で更新します。
do-while文を抜けたら後は経路を設定しているだけです。

さて、それでは探索アルゴリズムの1つであるベルマン・フォード法については以上です。