ダイクストラ法の時間計算量 (Big-O)
ダイクストラ法は非負辺のグラフで単一始点最短路を、二分ヒープを使って O((V + E) log V)、空間 O(V) で求めます。
インタラクティブな DevRef Hub を開く →主要データ
| 時間 (二分ヒープ) | O((V + E) log V) |
|---|---|
| 空間 | O(V) |
| 制約 | 辺の重みが非負 |
| 種別 | 単一始点最短路 |
よくある質問
ダイクストラ法の時間計算量は？
二分ヒープの優先度キューで O((V + E) log V) です。
なぜ辺の重みは非負でなければならない？
負の重みは貪欲法の前提を壊すため。Bellman-Ford を使います。
関連ページ
Dijkstra の計算量 は GOAT Lab の DevRef Hub の一部です。登録不要・オフラインでも使える無料リファレンスで、上のツールから任意の値を計算できます。
GOAT Lab の一部 — 科学・エンジニアリング・開発者向けの無料ブラウザツール26種。登録不要。