基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成15年 秋期 基本情報技術者 午後 問04
問04   最短経路を求めるプログラム

 次のプログラムの説明及びプログラムを読んで,設問に答えよ。

〔プログラムの説明〕 出発地から目的地までの最短経路を求める副プログラムである。

(1) 副プログラム SP は,N 個(N > 1)の地点で構成される図1のような 有向グラフで表される経路図において,地点1(出発地)から地点 N(目的地)までの 最短経路を求めて,出力するプログラムである。 なお,図1において,円は地点を,矢印の向きは進行方向を,矢印に付けた数字は 地点間の距離を表す。

(2) この副プログラムでは,次の配列を用いる。 要素番号 i,j の値は 1,2,…,N であり,各地点と対応している。

C[i, j]: 地点 i から地点 j までの距離を表す配列である。 地点 i から地点 j までの直接の経路がない場合,地点 i と地点 j が等しい場合, 及び進行方向と逆の場合は ∞ が格納されている。
例えば図1 では,C[1, 2] = 30,C[1, 3] = ∞,C[2, 1] = ∞,C[2, 2] = ∞ である。
D[i]: 地点1 から地点 i までの最短距離を格納するための配列である。 初期設定で地点1 から地点 i までの距離 C[1, i] を設定する。 例えば図1 の場合の初期設定では,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] だけに1を設定し,他のすべての要素には 0 を設定する。 最短経路を求めた後はすべての要素が1となる。
S[i]: 地点1から地点 i までの最短経路を求める過程で,地点 i の直前の地点を 格納するための配列である。 初期設定ではすべての要素に1を設定する。 例えば図1 の場合,最短経路を求めた後は S[2] = 1,S[3] = 4,S[4] = 1,S[5] = 3 となり, 地点 5 の直前は地点 3,地点3の直前は地点 4,地点。
W[i]: S[i] を用いて最短経路を出力する際に使用する作業用の配列である。

(3) 最短経路を求める手順は,次のとおりである。

@ 処理していないすべての地点(P[i] = 0)のうちで,D[T] が 最小である地点 T を選ぶ。

A 地点 T を処理済(P[T] = 1)とする。

B 処理していないすべての地点(P[i] = 0)に対して,D[T] + C[T, i] の値が D[i] の値より小さければ,D[T] + C[T, i] の値で D[i] を置き換える。

C Bで D[i] を置き換えた場合,S[i] に T を代入する。

D 処理 @ 〜 C を,全地点が処理済になるまで繰り返す。

(4) 最短経路を求めた後,配列 S を用いて最短経路を出力する。 出力には,数値 X を出力した後に改行する副プログラム Output(X) を利用する。

(5) 図1 の経路図に対する出力結果を図2 に,また最短経路を 求める過程での配列と変数 T の値の変化を表1 に示す。

(6) 出発地から目的地までの経路は,必ず存在するものとする。


図1 経路図の例(N = 5 の場合)

1                     
4                     
3                     
5                     

図2 図1の経路図に対する出力結果

   表1 図1の最短経路を求める過程の配列と変数 T の値の変化

(7) 副プログラム SP の引数は,表2のとおりである。

      表2 SP の引数
変数名 入力/出力 意  味
N 入力 地点数
C[,] 入力 地点間の距離を表す2次元の定数配列

〔プログラム〕

基本情報技術者試験


設問 プログラム中の に入れる正しい答えを,解答群の中から選べ。

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

解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]