キンサクプログラマー

お金儲けと技術のメモ

毎日アルゴリズム(第4日目)ダイクストラ法 その2

pikurusux.hatenablog.com
時間が開いたが実装してみた。
アルゴリズム自体はその1に乗っているので、詳細はそちらへ。
まともに動いているのか至極怪しいが、一応動く。
github.com


なんとなくポイント。

最短距離から計算しよう

常に最短のノードから計算する事で、成り立つ。
このポイントの効率的な実現手段としてプライオリティキューが用いられるのが一般的。
*逆にプライオリティキューを使わない場合は、最小コストノードの探索処理にnが必要になるので、かなり無駄。

プライオリティキュー

もっとも優先度の高いキューが先頭にくるキュー。
ただし、二番目以降の順番は保証されていない。
8.5. heapq — ヒープキューアルゴリズム — Python 3.6.1 ドキュメント

余談

某サイトの問題をダイクストラ法(プライオリティキュー版)で解いてみたら、マップ作成する段階でタイムアウトした・・・
ヒューリスティック探索したところで対して変わらないと思うのだが、そんな爆速で解ける方法なんてあんだっけ・・・

おかしいところとか、こうした方が良いよ!ってことがあれば教えてください!