フツーって言うなぁ!

フツーなサラリーマンのフツーな嘆き.

Pythonでダイクストラアルゴリズムを実装した

しばらく忙しくて,更新が途絶えてしまいました.
少なくとも今年度中は,2週間に1回更新を続けていきたいです.

本題.

競技プログラミングで,ダイクストラアルゴリズムを実装する機会があったので,ソースコードを載せておきます.

ダイクストラアルゴリズムとは?

ダイクストラアルゴリズム(ダイクストラ法)とは,重み付きグラフの探索アルゴリズムの一種で,すべての辺の重みが非負なグラフの単一始点最短経路問題を解くためのアルゴリズムです.
グラフの始点が与えられた時,そこから他の(すべての)頂点までの最短経路と,そこまでの重みの和(最短距離)を求めることができます.

ダイクストラ法 - Wikipedia

ナイーブなダイクストラアルゴリズムはO(|V|^2)ですが,プライオリティキュー(優先度付きキュー)と呼ばれるデータ構造を用いることで,O(|E|log|V|)程度で最短経路を求められます.

優先度つきキュー - Wikipedia

Pythonでプライオリティキューを実装する際には,heapqというモジュールを用いるのが一番良さそうです.
8.4. heapq — ヒープキューアルゴリズム — Python 2.7ja1 documentation
以下,使い方.

>>> import heapq
>>> q = [] # プライオリティキュー
>>> heapq.heappush(q, 1) # 1をpush
>>> q
[1]
>>> heapq.heappush(q, 2) # 2をpush
>>> q
[1, 2] # 1より2の方が優先度が低いので先頭以外に追加される
>>> heapq.heappush(q, 0) # 0をpush
>>> q
[0, 2, 1] # 0の優先度が最も高いので先頭に追加される
>>> heapq.heappop(q)
0
>>> q
[1, 2]

常に,先頭に最小(優先度最高)の要素が来るようになっています(それ以外の順序は保証されません).
ヒープを用いてインデックスを管理しているため,要素の追加,削除などの操作をO(log n)で行えるのが特徴です.

また,下記のように,Pythonでは,タプルを比較する時に,最初の要素から順に比較して大小を判定するらしいです.
今回は,プライオリティキューの優先度の計算にその性質を使っています.

>>> (1, 1) < (1, 2)
True
>>> (1, 1) < (0, 2)
False
>>> import heapq
>>> q = []
>>> heapq.heappush(q, (1, 1)) # (1, 1)をpush
>>> q
[(1, 1)]
>>> heapq.heappush(q, (0, 2)) # (0, 2)をpush
[(0, 2), (1, 1)] # (0, 2)の優先度が最も高いので先頭に追加される

実装


gistcca597c45148c5e55c3f

競技プログラミング用のライブラリにしたいということもあり,無駄な処理はなるべく省くようにしたつもりです.

また,これは,グラフの表現方法として隣接行列を用いた時の解法です.
隣接リストを用いると,少しコードが変わると思います.

参考

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?