ベルマンフォード法をPythonで実装して関数化する

hirohirohirohiros.hatenablog.com

概要

　ベルマンフォード法はダイクストラ法と同じ最短路を求めるアルゴリズムです．ダイクストラ法と違い，負辺が存在しても正しく動きます．また，負の閉路を検出することも出来ます．そのかわり，計算量はダイクストラ法より多いです．

アルゴリズムの内容

　閉路とはノードを移動していったら，元のノードに戻ってくるような道の事を言います．負の閉路とは，閉路を一周した時かかったコストが負になる閉路の事を言います．
　負の閉路が無いグラフを考えます．AとBのノードが辺で繋がっておりそのコストをCとすると，Bの(暫定)最短路は"Bの(暫定)最短路"と"Aの(暫定)最短路+C"のどちらか小さい方であると言えます．開始ノードの最短路を0，その他ノードを無限大に設定し，全ての辺に対してこの暫定最短路の更新(wikiでは緩和と言っていました)を行います．この処理をずっとループして行えばいずれ最短路が確定します．
　ではこのループを何回行えば最短路が確定するのでしょうか？もし，開始ノードから順に最短路になるような辺の順番で緩和したら1ループ目で最短路が確定することになります．もし，その真逆の順番で緩和を行ったら1ループ目では開始ノードとその次のノードしか確定しないことになります．つまり開始ノードと次のノードの2つは確定します．2ループ目では既に確定していた2ノードとさらに次のノードが確定することになります．よって，全てのノードを確定させるためにはノード数-1ループで全て最短路が確定します(開始地点はループ前から最短路0で確定しているので-1しています)．
　負の閉路があった場合、こうはなりません．緩和を行うたび負の閉路はよりマイナスのコストを返すため，永遠に緩和によって最短路が更新されます．よってノード数-1回目のループを超えて更新がされていたら，それは負の閉路があるということになります．
　これがベルマンフォード法です．全ての辺に対して緩和を試すのでO(E)，そのループをV-1回行うので，全体の計算量はO(EV)になります．

pythonコード

　以上を実装しました．ダイクストラ法と同じようにstart地点は指定できるようにしましたがデフォルトでは0にしています．ダイクストラ法とは隣接リストの入力形式が異なっています．

def bellmanford(edge, V, start=0):
    """ベルマンフォード法

    startノードを始点とし, 他のノードを終点として移動したとき, 通る辺のコストの和の最小値
    負辺が存在しても使える
    計算量: O(EV)

    Args:
        edge (list): ノードAからノードBに行くコストがXの時[A, B, X]. これを全ての辺についてまとめたリスト
        V (int): ノード総数
        start (int, optional): 始点のノード. Defaults to 0.

    Returns:
        list or -1: 負の閉路が存在しないとき
                        startノードから[0番目のノードに移動するコストの最小値, 1番目のノードに移動するコストの最小値, ...]
                        dist[start] = 0
                    負の閉路が存在するとき
                        -1
    """
    INF = 1<<60
    dist = [INF] * V
    dist[start] = 0

    for i in range(V):
        for from_node, to_node, cost  in edge:

            if dist[from_node] + cost < dist[to_node]:
                dist[to_node] = dist[from_node] + cost

                # V回目にも更新があったら負の閉路が存在する
                if i == V-1:
                    return -1

    return dist