ダイクストラ法
🤔 何が書いてあるの？
- ダイクストラ（Dijkstra）法の実装方法と特徴についてまとめる
🤔 何が大事なの？
- 優先度付きキューを使うことで，「探索済み」=「最短距離確定済み」となること．
- キューから取り出したときに最短距離を確定させること．
🤔 ダイクストラ法ってなに？
- グラフ上の2頂点間の最短距離を求めるアルゴリズム
- 幅優先探索，深さ優先探索は辺の長さが固定の場合，01-BFSは辺の長さが2値の場合に用いるのに対し，ダイクストラ法は辺の長さが任意の非負整数の場合に用いることができる
- 優先度付きキューを使って実装するのが一般的
🤔 どういう仕組み？
優先度付きキュー
スタックは後入れ先出し（LIFO），キューは先入れ先出し（FIFO）と，入れた順番で出す順番が決まる．優先度付きキューは，入れた要素の値の大きさによって順番が決まる．具体的には，要素の昇順または降順になるように入れる．要素を入れる際，順番決めに二分探索を使うので，O(logN)の計算量がかかる．
最短距離を記録する配列
始点から頂点iへの最短距離dを記録するための配列distを用意しておく．このときdist[i]=dとなる．なお，各要素の初期値は-1とするこれにより，
dist[i] == -1: 始点から頂点iへの最短距離はまだ確定していないdist[i] != -1: 始点から頂点iへの最短距離dist[i]で確定済み
と表現できる
始点から近い順に頂点を探索する
「始点から頂点番号iへ距離dで到達できる経路がある」とわかったら，優先度付きキューに (始点からの距離d, 頂点番号i)というタプルを入れる．優先度付きキューは，デフォルトでタプルを昇順に並べるので，キューの先頭ほど始点からの距離が近い頂点の情報が記録されている状態が保持される．
取り出した頂点への距離を確認・記録する
優先度付きキューの先頭のタプルを取り出す．これを(始点からの距離d, 頂点番号i)とする．このとき
dist[i] == -1: 始点から頂点iへの最短距離が決まっていないのでdist[i] = dとするdist[i] != -1: 始点から頂点iへの最短距離は決まっているので何もしない
とする．なお，頂点iへの最短距離を記録した後により短い最短距離が見つかることはない．なぜなら，もしそのような最短距離があるのであれば，優先度付きキューの並び替える機能によってそちらが先に取り出され，その時点で既に最短距離が記録されているはずだからである．つまり，「初めて最短距離が記録されるとき」=「真の最短距離が確定するとき」である．
最短距離を記録した頂点iに隣接する頂点を探索する
頂点iへの最短距離dが記録されたとき，頂点iに隣接するすべての頂点jについて，優先度付きキューに(d+頂点iから頂点jへの距離, 頂点j)というタプルを入れる．これは「始点から頂点番号jへ距離d+頂点iから頂点jへの距離で到達できる経路がある」とわかったからである．
⚡️ もっと速く！
上のアルゴリズムには無駄があるので，無駄を省くことで高速化できる
最短距離確定済みの頂点についてタプルを優先度付きキューに入れない
頂点iへの最短距離dを記録した後，頂点iと頂点jが隣接しているとき，タプル(d+頂点iから頂点jへの距離, 頂点j)を優先度付きキューに追加する．しかし，このとき既に頂点jへの最短距離が確定しているならば，このタプルは無駄になる（取り出されたときに最短距離確定済みとして捨てられる）．だったら入れなきゃいいじゃんということで，タプルを入れる前に「探索先の最短距離が確定しているか」ということをチェックし，確定していないときのみタプルを追加する．
参考