Dijkstra法のpythonでの実装

概要

　久しぶりにpythonをいじったので，リハビリがてらDijkstra法を実装しました．交通計画でも用いる基本的なアルゴリズムなので，ご参考ください．

Dijkstra法とは

　Dijkstra法（ダイクストラ法）は，最短経路探索の代表的な方法．リンクコストがすべて非負（0以上）のときに使える．
　ここでは詳細なアルゴリズム等については触れませんが，アルゴリズムの理解にはこちらのページが参考になります．
ダイクストラ法（最短経路問題）

pythonでの実装

対象ネットワーク

　ノード１を始点とする，下図のネットワークについてDijkstra法を適用します．

ソースコード

# coding: utf-8 #おまじない

#--------------------------------------------------
#◆最短経路探索問題
#--------------------------------------------------

#◆ネットワークの作成--------------------
node = [1,2,3,4,5,6]
linkcost = {(1, 2) : 30,
            (1, 3) : 25,
            (2, 3) : 40,
            (2, 4) : 35,
            (3, 5) : 15,
            (4, 6) : 45,
            (5, 4) : 10,
            (5, 6) : 40}
#{(リンクの起点，リンクの終点)：旅行時間}で表される有向リンクのdictionary．
link = list(linkcost.keys()) #linkcostのkeyからリンクのlistを生成．


#◆変数の準備----------------------------
startnode = 1 #始点ノード
inf = 999 #距離無限大を意味する，十分に大きな数
dist = {} #そのノードまでの距離を表す変数をdictionaryで用意
prev_node = {} #あるノードに最短経路で向かう際の直前のノード

#distに初期値を与える
for i in node:
    dist[i] = inf #初期値は距離無限大
dist[startnode] = 0 #始点のみ距離0

#undecided_distを定義する．
undecided_dist = dist.copy() #最短距離が未確定のノードとその距離．
 #辞書関数はミュータブルなオブジェクトのため，copy()メソッドを用いて複製する．

#prev_nodeに初期値を与える
for i in node:
    prev_node[i] = None


#◆本計算-------------------------------------
while undecided_dist: #最短距離が未確定のノードがなくなるまで繰り返す．
    u = min(undecided_dist, key=undecided_dist.get) #最短距離が未確定のノードのうち，距離が最小のノードを取り出す．
    del undecided_dist[u] #取り出したノードは未確定のノードから削除．
    for i in range(len(link)): #各リンクについて，
        if link[i][0] == u: #リンクの起点が，今取り出しているノードである場合，
            v = link[i][1] #リンクの終点に関して，その点までの距離を確認していく．
            if (dist[v] > dist[u] + linkcost[u,v]): #当該リンクを利用した経路の方が短い場合，
                dist[v] = dist[u] + linkcost[u,v] #距離を修正．
                prev_node[v] = u #そのノードに最短経路で向かう際の直前のノードを修正．


#◆出力---------------------------------------
print('answer =',dist)
print('prev_node =', prev_node)

結果

answer = {1: 0, 2: 30, 3: 25, 4: 50, 5: 40, 6: 80}
prev_node = {1: None, 2: 1, 3: 1, 4: 5, 5: 3, 6: 5}

ポイント

　今回はリンクコストを辞書形式とし，キーをリンクを表すタプル，値をリンクコストとした．これは，個人的に慣れていた表記で，見やすいという理由から．（あまり見かけない表記？）
　なお，今回のコードはオリジナルと呼ばれる，計算量がのもの．ヒープキューを用いることで，計算量を少なくする方法もあるので，計算速度を上げる必要がある場合はそちらを参照のこと．
　
　プログラミングについては初学者なので，もし間違い等あればご指摘ください．