基本情報技術者 予想問題｜A 第19問

解説

ダイクストラ法は、辺の重みが非負のグラフにおいて、単一の始点から他のすべての頂点への最短経路を求めるアルゴリズムであり、イが正解である。始点からの距離が未確定の頂点のうち最も距離が小さいものを順に確定していく貪欲法に基づいており、カーナビの経路探索やネットワークのルーティングプロトコル（OSPF）などに応用されている。アの連結成分を求める処理は深さ優先探索や幅優先探索で実現するものであり、ウの最小全域木（全頂点を最小コストの辺でつなぐ木）を求めるのはプリム法やクラスカル法である。エのハミルトン路は全頂点をちょうど一度ずつ通る経路を求める別の問題である。基本情報技術者試験では、「単一始点最短経路＝ダイクストラ法」「最小全域木＝プリム法・クラスカル法」という目的とアルゴリズムの対応が頻出ポイントである。