Dijsktra最悪の複雑さの入力シーケンス

Question

Dijsktrasの実際の複雑さはΘ（（e + v）logv）である通常のヒープで実装されたDijsktraアルゴリズムの入力シーケンスを探しています。

私はDijsktraをどのように実装するのか、それがどのように機能するのかを知っています。最も時間がかかる操作は、ヒープに頂点を追加し、頂点の距離を変更することです。しかし、私はDijkstraの最悪の場合の入力となるグラフ（グラフのシーケンス）を見つける方法がわかりません。

また、最悪の複雑さの入力シーケンスを見つける方法に関する一般的なヒントがある場合は、参考になります。

Answer 1

は頂点が1からnに番号が付けられ、あなたがnを頂点に、頂点1からのパスを見つけたいしましょう。 e[i][j]を端辺の長さとし、iとjを接続します。最初はe[1][2] = e[2][3] = ... = e[n - 1][n] = 1です。今度は、n - 2から1までの頂点を繰り返します。各jの番目の頂点では、[i + 2, n]にe[i][j] = e[i][i + 1] + e[i + 1][j] + 1となります。

今、私たちは完全なグラフを持っています。各反復でdijkstraはO(n)の頂点を更新するので、O(log n)で動作するO(n^2) = O(E)アクションです。

最終的な漸近線はO(n log(n) + E log(n))