Pythonでダイクストラアルゴリズムを実装した
しばらく忙しくて,更新が途絶えてしまいました.
少なくとも今年度中は,2週間に1回更新を続けていきたいです.
本題.
競技プログラミングで,ダイクストラアルゴリズムを実装する機会があったので,ソースコードを載せておきます.
ダイクストラアルゴリズムとは?
ダイクストラアルゴリズム(ダイクストラ法)とは,重み付きグラフの探索アルゴリズムの一種で,すべての辺の重みが非負なグラフの単一始点最短経路問題を解くためのアルゴリズムです.
グラフの始点が与えられた時,そこから他の(すべての)頂点までの最短経路と,そこまでの重みの和(最短距離)を求めることができます.
ナイーブなダイクストラアルゴリズムはO(|V|^2)ですが,プライオリティキュー(優先度付きキュー)と呼ばれるデータ構造を用いることで,O(|E|log|V|)程度で最短経路を求められます.
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)の優先度が最も高いので先頭に追加される
実装
競技プログラミング用のライブラリにしたいということもあり,無駄な処理はなるべく省くようにしたつもりです.
また,これは,グラフの表現方法として隣接行列を用いた時の解法です.
隣接リストを用いると,少しコードが変わると思います.
参考
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (33件) を見る