次のアルゴリズムの説明を読んで，設問１，２に答えよ。
〔アルゴリズムの説明〕
N 個（ N ＞１）の地点から構成されるグラフにおいて，出発地点からそれ以外の地点までの 最短距離を求めるアルゴリズム ShortestLength である。
(1) 図１に示す地点数 N＝６ のグラフを例として，ShortestLength を説明する。 図１において，丸は地点を，矢印の向きは進行方向を，矢印に付けた数字は地点間の距離を表す。
図１ グラフの例（地点数 N=6 ）
(2) ShortestLength では，次の配列を用いる。要素番号は 1，2，…，N で， 地点と対応している。配列の添字は１から始まる。
| Dt[i][j]： | 地点 i から地点 j までの距離が格納されている N×N 個の要素からなる配列。
地点 i から地点 j までの直接の経路がない場合，進行方向が逆向きの場合及び Dt[i][i] の場合には
∞（最大値を表す定数）が格納されている。図１の例では，Dt[i][j] の一部は次のとおりである。
Dt[1][3]＝∞， Dt[2][1]＝∞ |
| Sd[i]： | 出発地である地点１から地点 i までの仮の最短距離（以下，仮最短距離 という）を 格納する配列。初期設定ではすべての要素に∞を格納する。 |
| Pe[i]： | 最短距離を求める過程で処理済となった地点を識別するための配列。 初期設定ではすべて false に設定する。Pe[i] が true となったとき， Sd[i] には地点１から地点 i までの最短距離が求まっている。すべての 要素が true になると処理は終了する。 |
(3) 最短距離を求める手を，図１の例を使って示す。
図２ 手順①の結果
② 未処理の地点のうち，地点１からの仮最短距離が最も短い地点２（２は Pe[k]＝false かつ Sd[k] が最小となる添字 k の値）を選択し，Pe[2] を true にする。 この時点で，Sd[2]＝10 が地点１から地点２の間の最短距離として確定する。
次に，地点２から直接行ける地点３と地点５の仮最短距離 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
〔プログラムの一部〕
・Sd[i] ← min(Sd[i]， 
)
この結果を図３に示す。
図３ 手順②の結果
③ 未処理の地点のうち，仮最短距離が最も短い地点は，地点４と地点５の二つである。 このように複数ある場合は，要素番号の小さい地点４を選択し，処理済とする。 この時点で，Sd[4] が地点１から地点４の間の最短距離として確定する。
次に，地点４から直接行ける地点の仮最短距離を更新する。
Sd[4]＋Dt[4][5]＝40 となり，現在の Sd[5] の値より大きいので，更新しない。 この結果を図４に示す。
図４ 手順③の結果
④ 未処理の地点のうち，仮最短距離が最も短い地点５を選択し，処理済とする。
この時点で，Sd[5] が地点１から地点５の間の最短距離として確定する。
次に，地点５から直接行ける地点の仮最短距離を更新する。
Sd[3]＝50 → Sd[3]＝Sd[5]+Dt[5][3]＝30
Sd[6]＝∞ → Sd[6]＝Sd[5]+Dt[5][6]＝50
この結果を図５に示す。
図５ 手順④の結果
⑤ 未処理の地点のうち，仮最短距離が最も短い地点３を選択し，処理済とする。
この時点で，Sd[3] が地点１から地点３の間の最短距離として確定する。
次に，地点３から直接行ける地点６の仮最短距離を更新する。
手順③と同様に計算し，地点６の仮最短距離 Sd[6] の値は 
となる。
この結果を図６に示す。
図６ 手順⑤の結果
⑥ 未処理の地点のうち，仮最短距離が最も短い地点６を選択し，処理済とする。
この時点で，Sd[6] が地点１から地点６の間の最短距離として確定する。
すべての地点が処理済となったので終了となる。この結果を図７に示す。
図７ 手順⑥の結果
に入れる正しい答えを，解答群の中から選べ。
a に関する解答群
ウ Sd[k]＋Dt[i][k] エ Sd[k]＋Dt[k][i]
設問２ 次の記述中の
に入れる正しい答えを，
解答群の中から選べ。
図８のグラフの場合，出発地を地点１としてアルゴリズム ShortestLength を実行したとき， 最短距離が確定する順番は，次のとおりになる。
，地点６
また，配列 Sd の要素 Sd[3]，Sd[5] 及び Sd[6] の値は，
それぞれ 
，
及び
となる。
図８ グラフ
c に関する解答群
イ 地点２，地点４，地点５，地点３
ウ 地点４，地点２，地点３，地点５
エ 地点４，地点２，地点５，地点３
d～f に関する解答群
オ 70 カ 80 キ 190 ク 100
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
