競技プログラミング/問題/ダイクストラ法 - projecthikky @ ウィキ

概要

グラフのある始点から全ての頂点への最短距離を求めるアルゴリズム。
計算量は頂点数をN, 辺数をMとするとO((N+M)logN)。N,M <= 10^5程度のときに適用可能。
最短経路アルゴリズムの中で最も有名なアルゴリズムだと思われる。
全ての辺の重み（距離）が非負でないと適用できないことに注意。

実装はワーシャルフロイドに比べるとやや面倒。
計算量O((N+M)logN)を実現するためには優先度付きキューまたは二分ヒープを使う必要がある。
C++ならpriority_queue、pythonならheapqがあるのでそれを使おう。

分かりやすい解説など

ダイクストラ法（最短経路問題）
ダイクストラ法が分からなかった君のために - kuuso1のブログ

問題

Shortest Path - Single Source Shortest Path - AOJ
ABC035-D トレジャーハント