次のプログラムの説明及びプログラムを読んで，設問１，２に答えよ。
副プログラム ShortestPath は，Ｎ個（Ｎ＞１）の地点と，地点間を直接結ぶ経路及び 距離が与えられたとき，出発地から目的地に至る最短経路とその距離を求めるプログラムである。 最短経路とは，ある地点から別の地点へ最短距離で移動する際の経由地を結んだ経路である。 副プログラム ShortestPath では，出発地の隣接地点から開始して， 目的地に向かって最短距離を順次確定する。ある地点の隣接地点とは， その地点から他の地点を経由せずに直接移動できる地点のことである。
図１は，地点数Ｎが７の経路の例で，経路をグラフで表現したものである。 図１において，丸は地点を示し，各地点には 0 から始まる番号（以下，地点番号という）が 順番に割り当てられている。線分は地点間を直接結ぶ経路を示し，線分の上に示す数字はその距離を表す。 また，経路上は，双方向に移動できる。
図１ 地点数Ｎが７の経路の例
〔プログラムの説明〕
(1) 副プログラム ShortestPath の引数の仕様を，表１に示す。ここで， 出発地から目的地までを結ぶ経路は，少なくとも一つ存在するものとする。 また，配列の要素番号は，0 から始まる。
(2) Distance[i][j] (i＝0, …, nPoint－1, j＝0, …, nPoint-1）には， 地点 i から地点 j までの距離が格納されている。ただし， 地点 i と地点 j が同一の地点の場合は 0，地点 i が地点 j の 隣接地点ではない場合は －1 が格納されている。 図１の例における配列 Distance の内容は，表２のとおりである。
(3) 行番号 5 ～ 10 では，変数，配列に初期値を格納する。
② 最短経路を返却する要素数が nPoint である配列 sRoute の全ての要素に 初期値として－1 を格納し，最短経路上の地点の地点番号が設定されていないことを示す。
③ 出発地から各地点までの最短距離を設定する配列を pDist とする。 pDist は１次元配列であり，要素数は nPoint である。配列 pDist の全ての要素に 初期値として∞を格納する。
④ 出発地から各地点までの最短距離が確定しているかどうかを識別するための配列を pFixed とする。pFixed は１次元配列であり，要素数は nPoint である。 配列 pFixed の全ての要素に初期値として false を格納し，最短距離が未確定であることを示す。 最短距離が確定したときに true を設定する。 例えば，出発地から地点 i までの最短距離が確定したとき，pFixed[i] は true となり， その最短距離は pDist[i] に設定されている。pFixed[i] が false の場合は， 地点 i までの最短距離は未確定であり，pDist[i] の値は最短距離として確定されていない。
(5) 行番号 12 ～ 39 の最短経路探索処理では，出発地から各地点までの最短距離を算出しながら， 最短経路を求める。
配列 pFixed を調べ，出発地から全ての地点までの最短距離が確定していれば， 最短経路探索処理を抜けて (6) に進む。
② 行番号 23 ～ 29
出発地からの最短距離が未確定の地点の中で，出発地からの距離が最も短い地点を探し， その地点を sPoint とし，その地点の最短距離を確定する。
③ 行番号 3Ø ～ 38
各地点に対して (ア)，(イ) を実行し，①に戻る。
(ア) 地点 sPoint の隣接地点であり，かつ，出発地からの最短距離が未確定であるかどうかを調べる。
(イ) (ア) の条件を満たす地点 j に関して，出発地から地点 sPoint を経由して地点 j に到達する経路の 距離を求め，その距離が既に算出してある pDist[j] よりも短ければ， pDist[j] 及び pRoute[j] を更新する。ここで，pDist[j] は，出発地から地点 j までの 仮の最短距離となる。pRoute[j] には，そのときの，地点 j の直前の経由地の地点番号を設定する。
〔プログラム〕
(行番号)
| 設問１ | プログラム中の に入れる正しい答えを， 解答群の中から選べ。 |
a に関する解答群
ウ pFixed[i] エ pFixed[j]
b に関する解答群
エ sp オ sPoint
c，d に関する解答群
オ sRoute[dp] カ sRoute[i] キ sRoute[j] ク sRoute[sp]
| 設問２ | 次の記述中の に入れる正しい答えを，解答群の中から選べ。
図１において，出発地の地点番号 sp の値が 0，目的地の地点番号 dp の値が 6 の場合について， プログラムの動きを追跡する。行番号 12 ～ 39 の最短経路探索処理の繰返しで， 行番号 28 の α において sPoint に代入された値は，繰返しの１回目は 0， ２回目は 1，３回目は e となる。また，行番号 3Ø ～ 38 の処理が 終了した直後の β における配列 pDist と配列 pRoute の値を，表３に示す。 最短経路探索処理の繰返しが３回目のときの β における配列 pDist の値は f となり，配列 pRoute の値は g となる。 ここで，配列 pRoute の全ての要素には初期値として 0 が格納されているものとする。 |
e に関する解答群
f に関する解答群
イ 0, 2, 8, 4, 5, 10, ∞
ウ 0, 2, 8, 4, 5, 11, 14
エ 0, 2, 8, 4, 5, 11, ∞
オ 0, 2, 8, 4, 5, 12, 14
カ 0, 2, 8, 4, 5, 12, ∞
g に関する解答群
イ 0, 0, 0, 0, 1, 3, 5
ウ 0, 0, 0, 0, 2, 2, 0
エ 0, 0, 0, 0, 2, 2, 5
オ 0, 0, 4, 0, 1, 2, 0
カ 0, 0, 4, 0, 2, 2, 5
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
