ダイクストラ法をPythonで実装
ダイクストラ法
ダイクストラ法はグラフ理論における最短経路問題を解くためのアルゴリズムであり，
エッジでつながれたノード間の最短経路を導出することができる．
今回はダイクストラ法をPythonで実装した．
実装の中身としては，必要最低限のアルゴリズムとなっている．
実際の経路計画問題などではスタートからゴール間に通過するノード情報や，ノードの座標情報などが必要となることが多い．
ダイクストラ法の詳細に関しては，ネット上にいくらでも存在するのでここでは触れない．
ノードとエッジの設定
今回扱うグラフはヨビノリさんの動画にダイクストラ法の解説があるので，今回はそれに登場するグラフを用いる．
そのグラフが以下のようになっている．
〇に囲われたS,A~Gがノードで，ノードをつなぐ直線に振ってある数字がノード間のコストである．
開始時点では開始ノードから各ノードへの移動コストが不明なので，以下のように設定する．
Sはスタート地点なので0とし，それ以外は無限大として初期設定する．
import numpy as np
node_l = {
"S":0,
"A":np.inf,
"B":np.inf,
"C":np.inf,
"D":np.inf,
"E":np.inf,
"F":np.inf,
"G":np.inf
}
エッジ情報を以下のように記述する．
これによってあるノードに接続されているノード情報を表現する．
edge = {
# 構成
# 基点ノード:{"接続ノード1":コスト, "接続ノード2":コスト, ....}
"S":{"A":5, "B":4, "C":1},
"A":{"S":5, "D":2},
"B":{"S":4, "D":5, "E":6},
"C":{"S":1, "B":2},
"D":{"A":2, "B":5, "F":1, "G":3},
"E":{"B":6, "G":2},
"F":{"D":1, "G":3},
"G":{"D":3, "E":2, "F":4}
}
アルゴリズム
アルゴリズムの手順
- 未確定ノードの中からエッジが最小となるノードが選択される．
- 選択されたノードに繋がっているのノードの値を更新する．
- 選択されたノードの値が確定されるので，探索候補から削除する．
この手順を繰り返すことにより，スタートノードから目標ノードまでの最短経路が求まる．
ノードの更新
ノードの更新手順を下図に示す．下図の番号はアルゴリズムの実行順になっている．
- Sが最小なので値が確定．Sに繋がっているノードの値の更新．繋がっているノードABCの更新．
- Cが最小なので値が確定．Cに繋がっているノードの値の更新．繋がっているノードBの更新．
これを順番に繰り返していくことで各ノードの最短経路が導出される．
以下のpythonスクリプトを実行することで，図の順番通りの探索アルゴリズムを実行することができる．
import numpy as np
node_l = {
"S":0,
"A":np.inf,
"B":np.inf,
"C":np.inf,
"D":np.inf,
"E":np.inf,
"F":np.inf,
"G":np.inf
}
# 確定したルート
node_l_ = {}
edge = {
"S":{"A":5, "B":4, "C":1},
"A":{"S":5, "D":2},
"B":{"S":4, "D":5, "E":6},
"C":{"S":1, "B":2},
"D":{"A":2, "B":5, "F":1, "G":3},
"E":{"B":6, "G":2},
"F":{"D":1, "G":3},
"G":{"D":3, "E":2, "F":4}
}
while True:
# 未確定ノードの中からルートが最小のノードの選択
if len(node_l) == 1:
min_edge = list(node_l.keys())[0]
else:
min_edge = min(node_l, key=node_l.get)
# 探索したノード間のルートの削除
del_list = []
for i in edge:
for j in edge[i]:
if j == min_edge:
del_list.append(i+j)
for i in del_list:
del edge[i[0]][i[1]]
# 探索したノードのコストが以前のものより小さければ更新する
for i,j in edge[min_edge].items():
if (j + node_l[min_edge]) < node_l[i]:
node_l[i] = j + node_l[min_edge]
# 確定したノードへのルートの削除
node_l_[min_edge] = node_l[min_edge]
if len(edge) == 1:
break
del edge[min_edge]
del node_l[min_edge]
print("未確定のノード ", end="")
print(node_l)
print("確定したノード ", end="")
print(node_l_)
print("-"*100)
print("確定したノード ", end="")
print(node_l_)
実行すると下記の出力となる．
未確定のノード {'A': 5, 'B': 4, 'C': 1, 'D': inf, 'E': inf, 'F': inf, 'G': inf}
確定したノード {'S': 0}
----------------------------------------------------------------------------------------------------
未確定のノード {'A': 5, 'B': 3, 'D': inf, 'E': inf, 'F': inf, 'G': inf}
確定したノード {'S': 0, 'C': 1}
----------------------------------------------------------------------------------------------------
未確定のノード {'A': 5, 'D': 8, 'E': 9, 'F': inf, 'G': inf}
確定したノード {'S': 0, 'C': 1, 'B': 3}
----------------------------------------------------------------------------------------------------
未確定のノード {'D': 7, 'E': 9, 'F': inf, 'G': inf}
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5}
----------------------------------------------------------------------------------------------------
未確定のノード {'E': 9, 'F': 8, 'G': 10}
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5, 'D': 7}
----------------------------------------------------------------------------------------------------
未確定のノード {'E': 9, 'G': 10}
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5, 'D': 7, 'F': 8}
----------------------------------------------------------------------------------------------------
未確定のノード {'G': 10}
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5, 'D': 7, 'F': 8, 'E': 9}
----------------------------------------------------------------------------------------------------
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5, 'D': 7, 'F': 8, 'E': 9, 'G': 10}
図のような手順で更新されていることが確認できたと思います．
参考
グラフ理論⑤(ダイクストラのアルゴリズム)(Youtube)
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
ダイクストラ法(Wikipwdia)
Discussion