【競プロ】ダイクストラ法を正確に書く（O((M+N)log N) のつもりが Θ(N^2 log N) になっていた話）

はじめに

競技プログラミングをやっている高校生のButterFlvです！！内容はタイトルにある通りです。トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362） の D - Shortest Path 3 でダイクストラ法の実装が不完全であったためTLEしてしまったのでちゃんとダイクストラできるために書きます。

ダイクストラ法について

ダイクストラ法はBFSの拡張で動的計画法の一種です。単一の始点からの距離を各頂点について高速に求めることができます。使える条件は

• 負のコストの辺を持たない

です。頂点の数を $N$ 辺の数を $M$ として大体、ナイーブ $O(N^2)$ でpriority queueを使うと $O((M+N)\log N)$ です。

疑似コード

頂点に $0,1,2,\cdots ,N-1$ と番号をつけて, $\mathrm{edge}[v]$ を頂点 $v$ を始点とする辺の集合とし, 各辺は $(辺の終点, 辺のコスト)$ の形式で持ちます。また始点を $0$ とします。（このようにしてもアルゴリズムとして一般性を失いません。）

1. $\mathrm{dist}[v]_{(0\le v\lt N)} \gets \mathrm{inf}\ と初期化する.$
2. $\mathrm{dist}[0] \gets 0$
3. $\mathrm{used}[v]_{(0\le v\lt N)} \gets \mathrm{false}\ と初期化する.$
4. $\mathrm{queue}\gets_{\mathrm{push}}(\mathrm{dist}[0], 0)$ （$\mathrm{queue}$は最小ヒープ）
5. $\mathrm{queue}が空でないならループ$
   1. $(\mathrm{vdist}, v)\gets_{\mathrm{pop}} \mathrm{queue}$ （先頭の要素を消去）
   2. $\mathrm{used}[v]=\mathrm{true}\ なら次のループに移る.$
   3. $\mathrm{used}[v]\gets\mathrm{true}$
   4. $\mathrm{foreach}\ (nv, \mathrm{cost})\gets\mathrm{edge}[v]$
      1. $\mathrm{dist}[nv]\le\mathrm{dist}[v]+\mathrm{cost}$ なら次のループに移る.
      2. $\mathrm{dist}[nv]\gets\mathrm{dist}[v]+\mathrm{cost}$
      3. $\mathrm{queue}\gets_{\mathrm{push}}(\mathrm{dist}[nv],nv)$

注意ポイント

前章のコードのうち、一行でも抜けると $O((M+N)\log N)$ が保証されません。特に忘れがちなのは $\mathrm{used}$ の存在です。（ただし、$\mathrm{used}$ がなくても有限の時間で正当な解を出力します。）$\mathrm{used}$ がないときの撃墜ケースを考えてみましょう。例えば以下の場合です。

問題文

$N$ 頂点 $M$ 辺からなる単純連結無向グラフが与えられるので頂点 $1$ から頂点 $N$ までの最短経路を求めてください。
$i\ (1\le i\le M)$ 番目の辺は頂点 $u_i$ と $v_i$ を結び、そのコストは $w_i$ です。

制約

• $2\le N\le 2\times 10^5$
• $N-1\le M\le 2\times 10^5$
• $1\le u_i,v_i \le N$
• $0\le w_i \le 10^9$
• 入力はすべて整数

入力

入力は以下の形式で与えられます。

$N\quad M$
$u_1\quad v_1\quad w_1$
$u_2\quad v_2\quad w_2$
$\vdots$
$u_M\quad v_M\quad w_M$

撃墜ケース

$100005\quad 200000$
$1\quad 2\quad 1$
$1\quad 3\quad 2$
$1\quad 4\quad 3$
$\vdots$
$1\quad 100004\quad 100003$
$100005\quad 100004\quad 2$
$100005\quad 100003\quad 4$
$100005\quad 100002\quad 6$
$\vdots$
$100005\quad 2\quad 200006$

図にしてみるとわかりやすいかもしれません。コストをうまく調整することでキューに $N-2$ 回、頂点 $N$ を追加させることができ、頂点の探索順が $$1\to 2\to 3\to\cdots\to N-1\to \underbrace{N\to N\to\cdots\to N}_{N-2個}$$

となります。ここで、$\mathrm{used}$ がない場合は頂点 $N$ を探索するそれぞれのループで頂点 $2,3,4,\cdots ,N-1$ を走査することになり、このアルゴリズムは $\Theta(N^2\log N)$ になってしまいます。（本問の制約下だと全然ダメ）

さいごに

• おそらく、きちんとアルゴリズムを学んでいらっしゃる方であればこれくらい当たり前のことかと思いますが僕はハマってしまったので意外と忘れがちなポイントなのかな(?)と思いました
• A~Dは確実に迅速に、沼らずとれるよう、基礎的なアルゴリズムも時々復習しておきたいですね～