Pythonで学ぶアルゴリズム 第24弾：ベルマン・フォード法

#Pythonで学ぶアルゴリズム< ベルマン・フォード法 >

##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第24弾としてベルマン・フォード法を扱う．

##ベルマン・フォード
今回から，最適経路に関するアルゴリズムを扱っていくが，その１つ目としてベルマン・フォード法を扱う．
いま，次に示すような経路において，最短経路となるときの距離（コスト）を求めたい．

丸で囲まれたところは目的地であり，それらを結ぶ矢印が道とする．矢印の近くにある数値はその道（矢印）を通る時の距離（コスト）である．また矢印には始点と終点があり，逆走はしないものとする．この経路に対して，ベルマン・フォード法を適用していく．

ベルマン・フォード法とは，始点地におけるコストと道でのコストを足し合わせた結果，終点地のコストよりも小さければ，その終点地のコストを更新していくというものである．いま示した経路において，最短経路を見つけていく様子をひとつひとつ以下に示す．なお，各目的地における初期値はスタート地点以外∞としている．

このようにして各目的地における最短距離（最小コスト）が求められる．以下の実装では，その各目的地における最短距離を出力するものとする．また，∞の表現について，Pythonではfloat('inf')とすることで，表現できるようだが，ほかの言語では，9999999のように十分大きな数値として行えばよいらしい．単純に初期値は更新されるものとして大きな値にしておくということに変わりはない．

##実装
先ほどの説明をもとに，実装した．以下にソースコードとそのときの出力を示す．

#####ソースコード

bellman_ford.py

"""
2021/01/28
@Yuya Shimizu

ベルマン・フォード法
"""

def bellman_ford(Map, num_node):
    """ 経路の表現
            [始点, 終点, 辺の値]
            A, B, C, D, ... → 0, 1, 2, ...とする """
    node = [float('inf') for i in range(num_node)]  #スタート地点以外の値は∞で初期化
    node[0] = 0     #スタートの始点は0で初期化

    Continue = True #終了条件を表す変数　Falseとなれば終了
    
    while Continue:
        Continue = False

        #経路の要素を各変数に格納することで，視覚的に見やすくする
        for factor in Map:
            start = factor[0]   #始点
            goal  = factor[1]   #終点
            cost  = factor[2]   #コスト

            #更新条件
            if node[start] + cost < node[goal]:
                node[goal] = node[start] + cost     #更新
                Continue = True

    return node

if __name__ == '__main__':
    MAP = [[0, 1, 4], [0, 2, 3], [1, 2, 1], [1, 3, 1],
               [1, 4, 5], [2, 5, 2], [4, 6, 2], [5, 4, 1], [5, 6, 4]]

    #今の目的地の数は7つ（0~6: A~G）
    opt_node = bellman_ford(MAP, 7)
    print(opt_node)

#####出力

[0, 4, 3, 5, 6, 5, 8]

はじめに図で示した通り，[A, B, C, D, E, F, G] = [0, 4, 3, 5, 6, 5, 8]というように各目的地における最短距離を出力できていることが分かる．

##感想
ベルマン・フォード法は今まで知らなかった．また，Pythonに∞表現があることも知らなかった．最短距離問題は距離をコストとすることで，ほかにも応用できるし，そもそも問題が面白かった．前回までの並べ替えとは少し雰囲気が変わり，また士気が高まり，次回からの学習も楽しみである．

##参考文献
Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社