ダイクストラ法 (グラフ中のどのエッジもそこを通るコストが0以上であるときに、ある始点ノードから他のノードに至る経路でコストが最小のものを特定できるアルゴリズム) の Python スクリプトとそれを可視化する Python スクリプトです。
参考文献
- Dijkstra's Algorithm： ダイクストラ法の実装はこちらの津田塾大学の新田先生のページを前面的に参考にさせていただきました。
スクリプト
-
CookieBox26/dijkstra.py： こちらの Gist に以下の2つの Python ファイルがあります。
- dijkstra.py： ダイクストラ法で最適経路を解くスクリプトです。優先度付きキュー (Python 標準の queue.PriorityQueue； 二分ヒープのはず) を用いた、計算量が $O((E+V)\log {V})$ になる版です (エッジがとても密でない限り単純探索より速い)。
- dijkstra_drawer.py： ダイクストラ法の問題や答えを可視化するスクリプトです (NetworkX 使用)。上記のスクリプトで経過をロギングしておくと経過を可視化することもできます。グラフのレイアウトが気に入らない場合は seed をふってください。
スクリプトの使い方
前提として、問題は以下の形式のテキストファイルで与えることとします (参考文献に準拠しています)。
6 10 # ノード数, エッジ数
0 1 10 # 始点, 終点, 通過コスト (以下, エッジ数だけ繰り返し)
0 2 5
0 3 1
1 2 4
1 4 10
2 3 5
2 4 10
2 5 17
3 5 17
4 5 2
0 5 # 最適経路を求めるべき区間
問題ファイルと2つの Python ファイルを隣に置いて、ノートブックで例えば以下のように実行します。
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Rounded Mplus 1c'
# スクリプトから必要な関数を読み込み
from dijkstra import load_question, solve
from dijkstra_drawer import draw
question_filename = 'data.txt'
g, i_start, i_end = load_question(question_filename) # 問題ファイルを読み込み
solution, path_, log_ = solve(g, i_start, i_end, logging=True) # ダイクストラ法で解く
print('◆ 最小コストおよびそのときのパス\n', solution, path_)
print('◆ キュー状態のログ (コスト, ノード, どこから)\n' + '\n'.join([f'({i+1}) {q}' for i, q in enumerate(log_)]))
draw(plt, question_filename) # 単にグラフを描画
draw(plt, question_filename, path_) # 最適経路を装飾
draw(plt, question_filename, path_, log_, n_cols=3, figsize=(3, 3)) # 経過をすべて描画
そうすると、以下のように答えが出力されます。
◆ 最小コストおよびそのときのパス
17 [0, 2, 4, 5]
◆ キュー状態のログ (コスト, ノード, どこから)
(1) [(0, 0, None)]
(2) [(1, 3, 0), (10, 1, 0), (5, 2, 0)]
(3) [(5, 2, 0), (10, 1, 0), (6, 2, 3), (18, 5, 3)]
(4) [(6, 2, 3), (9, 1, 2), (18, 5, 3), (10, 1, 0), (15, 4, 2), (22, 5, 2)]
(5) [(9, 1, 2), (10, 1, 0), (18, 5, 3), (22, 5, 2), (15, 4, 2)]
(6) [(10, 1, 0), (15, 4, 2), (18, 5, 3), (22, 5, 2), (19, 4, 1)]
(7) [(15, 4, 2), (19, 4, 1), (18, 5, 3), (22, 5, 2)]
(8) [(17, 5, 4), (18, 5, 3), (22, 5, 2), (19, 4, 1)]
以下のように問題、答え、経過の画像も出力されます。
画像の左上の番号はキュー状態のログの番号と対応しています。凡例は以下です。
- 緑のノードとエッジ： 既に最小コストが確定しているノード及びそこまでのパス
- 黄のノードとエッジ： このステップで最小コストが確定するノード及びそこまでのパス
- 橙のノードとエッジ： 暫定コストが判明しているノード及びそこまでのパス
- 灰のエッジ： このステップで捨てられるパス
経過の画像の解説
そもそもダイクストラ法は、「始点ノードからの最小コストが確定できるノードから確定させていく」といった方法です。
優先度付きキューを用いたダイクストラ法は、まず最初に「始点ノード自身にはコスト0で行ける」つまりここでは、(コスト0で, ノード0に行ける, None) をキューにプッシュして開始します (第3成分はどのノードからきたかなので最初は None )。タプルの最初の要素であるコストが優先度キーになります。そして、キューから要素を取り出すときは最もコストの低い要素が取り出せます。というか。最もコストの低い要素しか取り出せません。
(1) いまキューから要素を取り出すと (コスト0で, ノード0に行ける, None) が取り出せます (これしか入っていないので)。これをノード0への最小コストとして確定させます (コストが負のエッジがない前提なので、あえて他のノードを巡ってきた方がコストが小さくなるということはなく、最小コストとして確定させるのに差支えはないでしょう)。そして、いま最小コストが確定したノード0から直結するノードについて、ノード0から直行したときのコストを暫定コストとしてプッシュします。つまり、以下の3要素をプッシュします。
(コスト10で, ノード1に行ける, ノード0から)(コスト5で, ノード2に行ける, ノード0から)(コスト1で, ノード3に行ける, ノード0から)
(2) いまキューから要素を取り出すと、暫定コストのうち最小の (コスト1で, ノード3に行ける, ノード0から) が取り出せます。これをノード3への最小コストとして確定させます (なぜなら、もしノード0以外からノード3に行くならば、必ず他の暫定コストを経由しなければならないからです！)。そして、いま確定したノード3から直結する未確定ノードについて、ノード3から直行したときのコストを暫定コストとしてプッシュします。
(コスト6で, ノード2に行ける, ノード3から)(コスト18で, ノード5に行ける, ノード3から)
(3) いまキューから要素を取り出すと、暫定コストのうち最小の (コスト5で, ノード2に行ける, ノード0から) が取り出せます。これをノード2への最小コストとして確定させます (なぜなら、もしノード0以外からノード3に行くならば、必ず他の暫定コストを経由しなければならないからです！)。そして、いま確定したノード2から直結する未確定ノードについて、ノード2から直行したときのコストを暫定コストとしてプッシュします。
(コスト9で, ノード1に行ける, ノード2から)(コスト15で, ノード4に行ける, ノード2から)(コスト22で, ノード5に行ける, ノード2から)
(4) いまキューから要素を取り出すと、暫定コストのうち最小の (コスト6で, ノード2に行ける, ノード3から) が取り出せます。しかし、ノード2への最小コストは (3) で既にノード0から行くパスと確定しています。であれば、もはやノード3からノード2に行く意味はないので、この要素は単に捨てます。
(5) いまキューから要素を取り出すと、暫定コストのうち最小の (コスト9で, ノード1に行ける, ノード2から) が取り出せます。これをノード1への最小コストとして確定させます (略)。そして、いま確定したノード1から直結する未確定ノードについて、ノード1から直行したときのコストを暫定コストとしてプッシュします。
(コスト19で, ノード4に行ける, ノード1から)
以降は同様の手続きの繰り返しなので省略します。最終的に終点であるノード5への最小コストが17で確定します。
なお、この記事の例では終点ノードへの最小コストが確定したときにすべてのノードへの最小コストが確定しますが、グラフによっては未確定ノードが残ります。 もっとも、未確定ノードを残したくなければ未確定ノードがなくなるまでアルゴリズムを続けてもいっこうにかまいません。この記事にリンクしてあるコードは終点ノードへのコストが確定したら終わるようになっています (該当箇所)。