頂点数 V、辺数 E のグラフに対するダイクストラ法で、暫定距離が最小の頂点を取り出す処理に2分ヒープを用いたときの時間計算量はどれか。

解説

正解は「$O((V+E)\log V)$」です。ダイクストラ法では、各頂点を1回ずつ取り出して確定し（V 回）、そのたびに隣接する辺をたどって距離を更新します（合計 E 回）。2分ヒープを使うと、最小値の取り出しと距離の更新がそれぞれ $O(\log V)$ で行えるので、全体で $O((V+E)\log V)$ になります。「$O(V^2)$」は、最小の頂点を毎回すべての頂点から線形に探す単純な実装の計算量で、辺が非常に多い密なグラフではこちらが有利なこともあります。「$O(VE)$」は、負の辺も扱えるベルマン・フォード法の計算量です。「$O(E)$」は、最小値を管理する手間を無視しています。