ネットワークスペシャリスト試験 令和6年度 春期 午前II 問5

【正解】エ

Aから各ノードへの累積コストが最小となる経路を順に確定します。最初は、AからBが1、Eが4、Dが7です。最小のBを確定すると、B経由のEは1＋2＝3、Cは1＋4＝5になります。次にEを確定すると、E経由のCは3＋1＝4、Dは3＋3＝6に更新されます。続いてCを確定しても、C経由のDは4＋3＝7なので、既存の6より小さくなりません。したがって、親子関係はA―B、B―E、E―C、E―Dとなります。DとEはスパニングツリー上で隣接するため、エが正解です。

アのAとEは誤りです。図では直接接続され、その区間のコストは4ですが、A―B―Eの累積コストは1＋2＝3です。Eの親はAではなくBになるため、ツリー上では隣接しません。

イのBとCは誤りです。A―B―Cの累積コストは1＋4＝5ですが、A―B―E―Cなら1＋2＋1＝4です。したがって、Cの親はBではなくEです。

ウのCとDは誤りです。C―Dの区間は存在しますが、AからCを経てDへ進む累積コストは1＋2＋1＋3＝7です。Eから直接Dへ進む経路は1＋2＋3＝6なので、Dの親はEとなります。

【ポイント】 スパニングツリーでは、元の図で直接つながっているだけでは隣接とは限りません。選ばれた最短経路上の辺かどうかを確認します。 ダイクストラ法では、未確定ノードのうち累積コストが最小のものを確定し、そのノードを経由する各コストを更新します。