ダイクストラ法

使用頻度が高い

以下の条件のときに主に用いられる

重みつきグラフ（有向でも無向でも良い）

単一始点最短経路問題

負のコストの辺を含まない

アルゴリズム

Priority queueでは最短距離順で情報がソートされるようにする

キューが空になるまで、次の操作を繰り返す

キューの先頭要素（最短距離の一番小さいもの）を取り出す

もし、記録してある最短距離より取り出した要素に入っている距離情報のほうが大きければ、ここで打ち切って先頭要素を取り出す操作に戻る

そこから移動できる頂点を走査し、最短距離が更新できるものがあれば、距離を更新してからその頂点への距離、頂点の情報をキューにpushする

負の閉路

計算量

$ O(ElogV)

参考