次のプログラムの説明及びプログラムを読んで，設問に答えよ。
〔プログラムの説明〕 出発地から目的地までの最短経路を求める副プログラムである。
(1) 副プログラム SP は，N 個（N ＞ １）の地点で構成される図１のような 有向グラフで表される経路図において，地点１（出発地）から地点 N（目的地）までの 最短経路を求めて，出力するプログラムである。 なお，図１において，円は地点を，矢印の向きは進行方向を，矢印に付けた数字は 地点間の距離を表す。
(2) この副プログラムでは，次の配列を用いる。 要素番号 i，j の値は 1，2，…，N であり，各地点と対応している。
| C[i, j]： |
地点 i から地点 j までの距離を表す配列である。
地点 i から地点 j までの直接の経路がない場合，地点 i と地点 j が等しい場合，
及び進行方向と逆の場合は ∞ が格納されている。 例えば図１ では，C[1, 2] ＝ 30，C[1, 3] ＝ ∞，C[2, 1] ＝ ∞，C[2, 2] ＝ ∞ である。 |
| D[i]： | 地点１ から地点 i までの最短距離を格納するための配列である。 初期設定で地点１ から地点 i までの距離 C[1, i] を設定する。 例えば図１ の場合の初期設定では，D[2] ＝ C[1, 2] ＝ 30，D[3]＝ C[1, 3] ＝ ∞， D[4] ＝ C[1, 4] ＝ 20，D[5] ＝ C[1, 5] ＝ 120 が設定される。 |
| P[i]： | 最短経路を求める過程で，処理済となった地点を識別するための配列である。 初期設定では P[1] だけに１を設定し，他のすべての要素には 0 を設定する。 最短経路を求めた後はすべての要素が１となる。 |
| S[i]： | 地点１から地点 i までの最短経路を求める過程で，地点 i の直前の地点を 格納するための配列である。 初期設定ではすべての要素に１を設定する。 例えば図１ の場合，最短経路を求めた後は S[2] ＝ 1，S[3] ＝ 4，S[4] ＝ 1，S[5] ＝ 3 となり， 地点 5 の直前は地点 3，地点３の直前は地点 4，地点。 |
| W[i]： | S[i] を用いて最短経路を出力する際に使用する作業用の配列である。 |
(3) 最短経路を求める手順は，次のとおりである。
① 処理していないすべての地点（P[i] ＝ 0）のうちで，D[T] が 最小である地点 T を選ぶ。
② 地点 T を処理済（P[T] ＝ 1）とする。
③ 処理していないすべての地点（P[i] ＝ 0）に対して，D[T] ＋ C[T, i] の値が D[i] の値より小さければ，D[T] ＋ C[T, i] の値で D[i] を置き換える。
④ ③で D[i] を置き換えた場合，S[i] に T を代入する。
⑤ 処理 ① ～ ④ を，全地点が処理済になるまで繰り返す。
(4) 最短経路を求めた後，配列 S を用いて最短経路を出力する。 出力には，数値 X を出力した後に改行する副プログラム Output(X) を利用する。
(5) 図１ の経路図に対する出力結果を図２ に，また最短経路を 求める過程での配列と変数 T の値の変化を表１ に示す。
(6) 出発地から目的地までの経路は，必ず存在するものとする。
図１ 経路図の例（N ＝ 5 の場合）
|
1 4 3 5 |
図２ 図１の経路図に対する出力結果
表１ 図１の最短経路を求める過程の配列と変数 T の値の変化
(7) 副プログラム SP の引数は，表２のとおりである。
| 変数名 | 入力／出力 | 意 味 |
| N | 入力 | 地点数 |
| C[,] | 入力 | 地点間の距離を表す２次元の定数配列 |
〔プログラム〕
設問 プログラム中の 
に入れる正しい答えを，解答群の中から選べ。
a ～ c に関する解答群
ア P[Y] ← 0 イ P[Y] ← 1 ウ S[T] ← Y
エ S[Y] ← T オ Y ← S[X] カ Y ← S[Y]
キ Z ← D[Y]
d に関する解答群
ア X ＞ 0 イ X ≧ 0 ウ W[X] ＞ 0 エ W[X] ≧ 0
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
