Dijkstraのアルゴリズム - 複雑さ

Question

私はDjisktraアルゴリズムの複雑さを理解し、誰かが私を訂正できることを願っています。

私の例では、n個の頂点を持つ完全なグラフを取りました。

開始頂点を選択し、a1とし、それをマークして、エッジのすべてのn-1ウェイトを計算します。 O（n）

あなたは最小のものを選びます。頂点a2とし、マークを付けましょう。 O（n）

その後、エッジでn-2個の新しい重みを計算し、次にマークされていない頂点を探して、マークされた頂点のセットを追加します。

など...

アルゴリズムは、すべての頂点をマークするまで実行されます。 O（n * ln（n））ではなく、O（n^2）にある複雑さ：n-1 + n-2 + ... + n - （n-1）= Binom欲しいです。

多くの人が最適化のためにヒープを使用していますが、私はまだBinom（n、2）計算を避ける方法は見当たりません。

私はある時点で間違っている必要がありますが、どこに見えません。

Answer 1

完全なグラフがあれば、O（n^2）よりもうまくいくわけではありません。これは入力のサイズなので、もちろんです。

完全なグラフがなく、隣接リストにエッジを格納している場合は、より効果的です。優先度キューを使用すると、O（e + n log n）を管理できます。ここで、eは隣接リストのエッジ数です。