[平成２９年度春] 午後 問8解説

[問題文・解答]

平成２９年度４月に実施された基本情報技術者試験の午後試験の問題・解答はIPA公式ページからダウンロード出来ます。（以下リンク）

[H29春 午後 問題文]　　　[H29春 午後 解答]

[問題概要]

この問題は、必須問題です。
出題分野はデータ構造及びアルゴリズムで、問題の題材は最短経路の探索です。

[設問1]

ダイクストラ法による最短経路探索のプログラムになります。
ダイクストラ法はスタート地点から距離の近い地点から順に最短経路を確定させ、その地点に隣接する地点の最短経路を必要に応じて更新していくことで、スタート地点から各地点への最短経路を求めていきます。

プログラムの詳細な処理の流れについてはP.36(3) 〜P.37(6)で説明されています。

a) 行番号23〜29の部分ではP.37(5)の②より出発地からの最短距離が未確定でかつ出発地からの距離の最も短い地点を探し、その地点をsPointとして最短距離を確定させます。aの部分では出発地からの最短距離が未確定かどうかの条件判定が入ります。プログラム内では配列pFixedによって各地点の最短距離の確定状態を格納しているため、
「イ」の「not(pFixed[j])」が適切です。

b) 29行目はsPointの最短距離の確定状態を更新する部分なので、bには「オ」の「sPoint」が適切です。

c,d) P.37(6)より行番号40で出発地から目的地までの最短距離をsDistに設定し、行番号41〜48で最短経路上の地点の地点番号を目的地から出発地までの順に配列sRouteに設定します。jはsRouteのインデックスとして使用し、iはsRouteに格納する最短経路上の地点番号として使用します。
配列pRouteには出発地から各地点への最短経路上で各地点に到達する直前の経由地が格納されており、iを目的地dpから開始して配列pRouteを辿ることにより最短経路上の地点を目的地から出発地までの順に求めることができます。従って、cには「sRoute[j]」が、dには「pRoute[i]」が当てはまります。

[答] a) イ　b) オ　c) キ　d) イ

[設問2]

表2の距離情報から地点間の配置・距離をグラフで表すと下図のようになります。

e) αでは、距離が未確定の地点のうち出発地から最も距離の近い地点をsPointに代入するので、グラフより3回目は地点3が当てはまります。

f,g) pDistは各地点の出発地からの最短距離（暫定）、pRouteには暫定の最短経路上で直前に通る地点番号を格納します。pDistの初期値は全て∞、pRouteの初期値は全て０です。
3回目の繰り返しでは、地点3の最短距離が確定し、地点3に隣接する地点5の暫定最短距離情報（pDist及びpRoute）が更新されます。暫定最短距離は4 + 8 = 12、直前の経由地は地点3なので、fには「カ」が、gには「ア」が当てはまります。

[答] e) イ　f) カ　g) ア

上記の解説は問題と解答を元に自分なりの考え方を記述しており、間違っている部分もあるかと思いますので、ご了承願います。また、誤りについては正しい考え方をご指摘・ご教授頂けると助かります。