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

平成20年 秋期 基本情報技術者 午後 問04
問04   最短距離を求めるアルゴリズム

 次のアルゴリズムの説明を読んで,設問1,2に答えよ。

〔アルゴリズムの説明〕

 N 個( N >1)の地点から構成されるグラフにおいて,出発地点からそれ以外の地点までの 最短距離を求めるアルゴリズム ShortestLength である。

(1) 図1に示す地点数 N=6 のグラフを例として,ShortestLength を説明する。 図1において,丸は地点を,矢印の向きは進行方向を,矢印に付けた数字は地点間の距離を表す。

      図1 グラフの例(地点数 N=6 )

(2) ShortestLength では,次の配列を用いる。要素番号は 1,2,…,N で, 地点と対応している。配列の添字は1から始まる。

Dt[i][j]: 地点 i から地点 j までの距離が格納されている N×N 個の要素からなる配列。 地点 i から地点 j までの直接の経路がない場合,進行方向が逆向きの場合及び Dt[i][i] の場合には ∞(最大値を表す定数)が格納されている。図1の例では,Dt[i][j] の一部は次のとおりである。

Dt[1][1]=∞, Dt[1][2]=10,
Dt[1][3]=∞, Dt[2][1]=∞
  Sd[i]: 出発地である地点1から地点 i までの仮の最短距離(以下,仮最短距離 という)を 格納する配列。初期設定ではすべての要素に∞を格納する。
  Pe[i]: 最短距離を求める過程で処理済となった地点を識別するための配列。 初期設定ではすべて false に設定する。Pe[i] が true となったとき, Sd[i] には地点1から地点 i までの最短距離が求まっている。すべての 要素が true になると処理は終了する。

(3) 最短距離を求める手を,図1の例を使って示す。

@ 出発地は地点1なので,Pe[1] に true を設定し,地点1から直接つながる 地点 2,4,5 までの距離 Dt[1][2], Dt[1][4],Dt[1][5] をそれぞれ Sd[2], Sd[4],Sd[5] に設定する。その結果,Sd[2]=10,Sd[4]=20,Sd[5]=30 となる。 この結果を図2に示す。地点 i の上又は下にある [] 内の数値は, 地点1から地点 i までの仮最短距離 Sd[i] を表し,網掛けの地点は処理済(Pe[i]=true)を表す。

      図2 手順@の結果

A 未処理の地点のうち,地点1からの仮最短距離が最も短い地点2(2は Pe[k]=false かつ Sd[k] が最小となる添字 k の値)を選択し,Pe[2] を true にする。 この時点で,Sd[2]=10 が地点1から地点2の間の最短距離として確定する。

 次に,地点2から直接行ける地点3と地点5の仮最短距離 Sd[i] を更新する。 ただし,Sd[i] の値が小さくならない場合は置き換えない。

(更新前)  (更新後)
Sd[3]=∞ → Sd[3]=Sd[2]+Dt[2][3]=50
Sd[5]=30 → Sd[5]=Sd[2]+Dt[2][5]=20

 このとき,地点 k( k =2)を経由する地点 i( i =3,5 )の仮最短距離 Sd[i] を 更新するための代入文を擬似言語で書くと,次の〔プログラムの一部〕のとおりになる。 ここで,関数 min は二つの引数のうち,小さい方の値を返すシステム関数である。

〔プログラムの一部〕

・Sd[i] ← min(Sd[i], )

この結果を図3に示す。

      図3 手順Aの結果

B 未処理の地点のうち,仮最短距離が最も短い地点は,地点4と地点5の二つである。 このように複数ある場合は,要素番号の小さい地点4を選択し,処理済とする。 この時点で,Sd[4] が地点1から地点4の間の最短距離として確定する。

 次に,地点4から直接行ける地点の仮最短距離を更新する。

 Sd[4]+Dt[4][5]=40 となり,現在の Sd[5] の値より大きいので,更新しない。 この結果を図4に示す。

      図4 手順Bの結果      

C 未処理の地点のうち,仮最短距離が最も短い地点5を選択し,処理済とする。

 この時点で,Sd[5] が地点1から地点5の間の最短距離として確定する。

 次に,地点5から直接行ける地点の仮最短距離を更新する。

  Sd[3]=50 → Sd[3]=Sd[5]+Dt[5][3]=30
  Sd[6]=∞ → Sd[6]=Sd[5]+Dt[5][6]=50

 この結果を図5に示す。

      図5 手順Cの結果

D 未処理の地点のうち,仮最短距離が最も短い地点3を選択し,処理済とする。

 この時点で,Sd[3] が地点1から地点3の間の最短距離として確定する。

 次に,地点3から直接行ける地点6の仮最短距離を更新する。

 手順Bと同様に計算し,地点6の仮最短距離 Sd[6] の値は となる。

 この結果を図6に示す。

      図6 手順Dの結果

E 未処理の地点のうち,仮最短距離が最も短い地点6を選択し,処理済とする。

 この時点で,Sd[6] が地点1から地点6の間の最短距離として確定する。

 すべての地点が処理済となったので終了となる。この結果を図7に示す。

      図7 手順Eの結果

設問1  アルゴリズム ShortestLength の説明中の に入れる正しい答えを,解答群の中から選べ。

a に関する解答群

ア Sd[i]+Dt[i][k]      イ Sd[i]+Dt[k][i]

ウ Sd[k]+Dt[i][k]      エ Sd[k]+Dt[k][i]

b に関する解答群 ア 30      イ 40      ウ 50      エ 60

基本情報技術者試験


設問2  次の記述中の に入れる正しい答えを, 解答群の中から選べ。

 図8のグラフの場合,出発地を地点1としてアルゴリズム ShortestLength を実行したとき, 最短距離が確定する順番は,次のとおりになる。

地点1,,地点6

 また,配列 Sd の要素 Sd[3],Sd[5] 及び Sd[6] の値は, それぞれ 及び となる。

     図8 グラフ

c に関する解答群

ア 地点2,地点4,地点3,地点5

イ 地点2,地点4,地点5,地点3

ウ 地点4,地点2,地点3,地点5

エ 地点4,地点2,地点5,地点3

d〜f に関する解答群

ア 30     イ 40     ウ 50     エ 60

オ 70     カ 80     キ 190     ク 100


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