ダイクストラ法

単一始点最短経路問題(SSSP)を解くためのアルゴリズムのひとつ。
ベルマンフォード法($O(|E|\times|V|)$)よりも高速に動作できる一方、グラフに負の辺がある場合利用できない。(性質上最短経路を確定できなくなる)

[実装 https://go.dev/play/p/dSjWm_VlUUi]

始点を始点からの最短経路がゼロと確定した頂点とし、他の頂点を未確定の頂点(始点からの距離が十分に大きい)とする。
最短経路が確定した頂点と最短経路が未確定の頂点との間の辺とその重みを集計し、重みが最小の辺につながる頂点を最短距離が確定した頂点とする。この条件が成立するのは負の辺が存在しない場合である。負の辺がなければ最短経路になるのは最小の重みの辺であることが一意にわかる。

愚直にすべての頂点に対して最短となる辺をすべての頂点で探索した場合、計算量は$O(|V|^2)$となる。
ヒープや優先度付きキューなどを使った場合、最短距離となる辺の探索が$O(log|V|)$で計算でき、これを辺の数だけその探索をおこなう。
このときの計算量は$O(|E|log|V|)$となり、辺の数が小さければ高速に動作する。

問題

参考