アルゴリズムとプログラミングアルゴリズムとデータ構造

重み付きグラフにおいて、ある始点から各頂点への最短経路を求めるアルゴリズムとして適切なものはどれか。ただし、辺の重みはすべて非負とする。

ア.クラスカル法

イ.ダイクストラ法正解

ウ.深さ優先探索

エ.バブルソート

解説

非負重みの単一始点最短経路はダイクストラ法の十八番。「いま最も近い未確定点」を順に確定していくナビゲーション戦略です。

なぜイが正解か

ダイクストラ法は始点からの暫定距離が最小の頂点を順に確定していく貪欲アルゴリズム。辺重みが非負であれば「いったん確定した距離は更新されない」という性質が保証され、各頂点ごとに正しい最短距離が求まります。実装は優先度付きキューで O((V+E) log V)。

なぜアは間違いか

クラスカル法は最小全域木（MST）を求めるアルゴリズム。辺を軽い順にソートしてサイクルを作らないよう選ぶ手法で、目的が「最短経路」とは別ものです。

なぜウは間違いか

深さ優先探索（DFS）は到達可能性の判定や連結成分の発見には便利ですが、重み付きグラフで最短距離を求める用途には向きません。重みを無視して進んでしまうため。

なぜエは間違いか

バブルソートは整列アルゴリズムで、そもそもグラフ問題ではありません。「最短経路」のキーワードに何か手当たり次第のアルゴリズムを当てたパターンの罠です。

出典: AI生成問題（学習用）

← 前の問題

O 記法（ビッグオー）に関する記述として、最も適切なものはどれか。

次の問題 →

動的計画法（DP）に関する記述として、最も適切なものはどれか。