No Caffeine, No Life

プログラミング(主にPython)

AOJ ALDS_1_12_C:単一始点最短経路 ダイクストラ法 (Dijkstra Algorithm)

AOJ ALDS 1_12_Bでは、O(|V^{2}|)のアルゴリズムだったが、優先度付キューを用いることでより高速化できる。

問題:

最短経路 | アルゴリズムとデータ構造 | Aizu Online Judge

ここでは、隣接リストと優先度付キュー(pythonでいうところのheapq)を用いる。この場合、|V|の数だけキューから頂点が取り出され、|E|の数だけキューに挿入されるので、O( (|V|+|E|) log |V| )になる。