プログラミングコンテストチャレンジブックのベルマンフォード法部分をpythonで

2016年8月15日プログラミング, python

以下二部グラフ判定に引き続き、ベルマンフォード法。

https://yutorinote.com/python-bipartite/

この部分の解説はやや不親切な印象です…。 アルゴリズム自体の説明はされてるけど、このアルゴリズムが妥当ですよっていう定性的な説明もないですし、数学的な証明もないので…。

書籍では構造体を利用してエッジを利用していますが、pythonでの実現方法をクラスにするか配列の配列にするか迷いました。前回せっかくnetworkxモジュールをインストールしたので、グラフ作る部分だけモジュールを利用することにしました。

# -*- coding:utf-8 -*-
import networkx as nx

def shortest_path(G, source):
    #扱いやすい形にする
    listG = nx.to_edgelist(G.to_directed())

    #STEP1:始点のコストd[source]を0に、それ以外をINFに
    INF = float("inf")
    d = [INF for f in range(G.order())]
    d[source] = 0;

    while True:
        update = False  #最小コストdが更新されたかどうかのフラグ
        for edge in listG:  #STEP2:各枝に対して、最小コストを更新する
            if d[edge[0]] != INF and d[edge[1]] > d[edge[0]] + edge[2]['weight']:#INFだと更新されないし、最大数INFに加算すると問題なので飛ばす
                d[edge[1]] = d[edge[0]] + edge[2]['weight']
                update = True   #STEP3-2:STEP2においてdが更新されていたらSTEP2を繰り返す
        if not update:
            break #STEP3-1:STEP2において最小コストdが更新されていなかったら停止
    return d



def main():
    #networkxモジュール使ってp94のグラフ作るよ
    G = nx.Graph()
    G.add_edge(0, 1, weight=2)
    G.add_edge(0, 2, weight=5)
    G.add_edge(1, 2, weight=4)
    G.add_edge(1, 3, weight=6)
    G.add_edge(1, 4, weight=10)
    G.add_edge(2, 3, weight=2)
    G.add_edge(3, 5, weight=1)
    G.add_edge(4, 5, weight=3)
    G.add_edge(4, 6, weight=5)
    G.add_edge(5, 6, weight=9)

    # 自作関数で、ノード0、6間の最小コストを表示する
    print "minimum cost(jisaku):", shortest_path(G, 0)[6]

    # モジュールを使って確認
    print "minimum cost(mocule):", nx.shortest_path_length(G,source=0,target=6,weight='weight')
    print "shortest path(module):", nx.shortest_path(G,source=0,target=6,weight='weight')

if __name__ == "__main__":
    main()

モジュールの方ではどのように実装しているのか確認してみてみたんですが、色々場合わけして、結局のところダイクストラ法の関数に渡してるみたいですね。

listG =[
 (0, 1, {'weight': 2}),
 (0, 2, {'weight': 5}),
 (1, 0, {'weight': 2}),
 (1, 2, {'weight': 4}),
 (1, 3, {'weight': 6}),
 (1, 4, {'weight': 10}),
 (2, 0, {'weight': 5}),
 (2, 1, {'weight': 4}),
 (2, 3, {'weight': 2}),
 (3, 1, {'weight': 6}),
 (3, 2, {'weight': 2}),
 (3, 5, {'weight': 1}),
 (4, 1, {'weight': 10}),
 (4, 5, {'weight': 3}),
 (4, 6, {'weight': 5}),
 (5, 3, {'weight': 1}),
 (5, 4, {'weight': 3}),
 (5, 6, {'weight': 9}),
 (6, 4, {'weight': 5}),
 (6, 5, {'weight': 9})
 ]

結局、上記を隣接リストとして使っているのですが、これを作るのにnetworkxモジュール使ってます(あとグラフの次数求めるのに)。どちらも書籍だと手入力で与えてるような箇所なので、モジュール使って楽しちゃってもいっかなと思って。