。

ダイクストラ法(Dijkstra)について。一日に１人２人はこの検索用語に引っかかってくるんだけど、何故こんなに？
で、ダイクストラ法の計算量オーダーについて書いてなかったので補足。
探索するグラフの頂点数n、辺数m、かつ>>>>mとする。
最後の条件が必要な理由は頂点数に対して辺の数が多い=密なグラフでは極端な場合となり下の結論が成り立たないため。

各データ構造ごとの、集合に対する操作delete_min, insert, member。その他データ構造を保つための処理。なんかの速度によって決まる。とりあえず結論だけ書いとくと

• 線形リスト。　　O()
• バイナリヒープ(Binary heap)。　　O(mlogn)
• フィボナッチヒープ(Fibonacci heap)。　　O(m+nlogn)

実用上最も高速なのはフィボナッチヒープとのこと。
ただ、フィボナッチヒープは結構複雑なアルゴリズムなので、バイナリヒープで十分、もしくはこっちのが速かったりする場合も。

フィボナッチヒープを使った場合のオーダーの右辺「nlogn」は見覚えがあると思うけど、結局delete_minで必要な最小コストをソートしておく部分に起因してる。要するにこれ以上どうしようもない。基数ソートみたいに別の制約を使えれば別だろうけど。

ただ、前書いたとおり、実用性はともかく線形時間でこれを解くアルゴリズムもあるみたいだけど。