問題
ダイクストラ法に関する記述として、誤っているものはどれか。
選択肢
- 1単一始点最短経路問題を解くアルゴリズムである
- 2辺の重みが負の値を含むグラフでも常に正しい結果を保証する
- 3優先度付きキューを用いると計算量は O((V+E) log V) となる
- 4貪欲法に基づくアルゴリズムである
正解
2. 辺の重みが負の値を含むグラフでも常に正しい結果を保証する
詳しい解説を見る解説を閉じる
解説
ダイクストラ法は単一始点最短経路問題を解く貪欲アルゴリズムだが、辺の重みに負の値が含まれる場合は確定済みノードを後から短縮する必要が生じるため正しく動作しない。負辺を含むグラフにはベルマン・フォード法（O(VE)）を用い、負閉路検出も可能。ダイクストラの計算量は単純実装で O(V^2)、二分ヒープ実装で O((V+E)log V)、フィボナッチヒープで O(E+V log V)。カーナビや IP ルーティング（OSPF）で実用化されている。
一問一答
全400問を繰り返し学習