基本情報技術者 2017年 春期 午後 問08

　副プログラムShortestPathは、N個（N > 1）の地点と、地点間を直接結ぶ経路及び距離が与えられたとき、出発地から目的地に至る最短経路とその距離を求めるプログラムである。最短経路とは、ある地点から別の地点へ最短距離で移動する際の経由地を結んだ経路である。副プログラムShortestPathでは、出発地の隣接地点から開始して、目的地に向かって最短距離を順次確定する。ある地点の隣接地点とは、その地点から他の地点を経由せずに直接移動できる地点のことである。 　図1は、地点数Nが7の経路の例で、経路をグラフで表現したものである。図1において、丸は地点を示し、各地点には0から始まる番号（以下、地点番号という）が順番に割り当てられている。線分は地点間を直接結ぶ経路を示し、線分の上に示す数字はその距離を表す。また、経路上は、双方向に移動できる。

〔プログラムの説明〕 (1) 副プログラムShortestPathの引数の仕様を、表1に示す。ここで、出発地から目的地までを結ぶ経路は、少なくとも一つ存在するものとする。また、配列の要素番号は、0から始まる。

(2) Distance[i][j]（i = 0, …, nPoint − 1; j = 0, …, nPoint − 1）には、地点iから地点jまでの距離が格納されている。ただし、地点iと地点jが同一の地点の場合は0、地点iが地点jの隣接地点ではない場合は−1が格納されている。図1の例における配列Distanceの内容は、表2のとおりである。

(3) 行番号5〜10では、変数、配列に初期値を格納する。 　① 最短距離を返却する変数sDistに初期値として∞（最大値を表す定数）を格納し、出発地から目的地までの最短距離が設定されていないことを示す。 　② 最短経路を返却する要素数がnPointである配列sRouteの全ての要素に初期値として−1を格納し、最短経路上の地点の地点番号が設定されていないことを示す。 　③ 出発地から各地点までの最短距離を設定する配列をpDistとする。pDistは1次元配列であり、要素数はnPointである。配列pDistの全ての要素に初期値として∞を格納する。 　④ 出発地から各地点までの最短距離が確定しているかどうかを識別するための配列をpFixedとする。pFixedは1次元配列であり、要素数はnPointである。配列pFixedの全ての要素に初期値としてfalseを格納し、最短距離が未確定であることを示す。最短距離が確定したときにtrueを設定する。例えば、出発地から地点iまでの最短距離が確定したとき、pFixed[i]はtrueとなり、その最短距離はpDist[i]に設定されている。pFixed[i]がfalseの場合は、地点iまでの最短距離は未確定であり、pDist[i]の値は最短距離として確定されていない。 (4) 行番号11では、出発地から出発地自体への最短距離pDist[sp]に0を設定する。 (5) 行番号12〜39の最短経路探索処理では、出発地から各地点までの最短距離を算出しながら、最短経路を求める。 　① 行番号13〜22 　　配列pFixedを調べ、出発地から全ての地点までの最短距離が確定していれば、最短経路探索処理を抜けて(6)に進む。 　② 行番号23〜29 　　出発地からの最短距離が未確定の地点の中で、出発地からの距離が最も短い地点を探し、その地点をsPointとし、その地点の最短距離を確定する。 　③ 行番号30〜38 　　各地点に対して(ア)、(イ)を実行し、①に戻る。 　　(ア) 地点sPointの隣接地点であり、かつ、出発地からの最短距離が未確定であるかどうかを調べる。 　　(イ) (ア)の条件を満たす地点jに関して、出発地から地点sPointを経由して地点jに到達する経路の距離を求め、その距離が既に算出してあるpDist[j]よりも短ければ、pDist[j]及びpRoute[j]を更新する。ここで、pDist[j]は、出発地から地点jまでの仮の最短距離となる。pRoute[j]には、そのときの、地点jの直前の経由地の地点番号を設定する。 (6) 行番号40〜48では、出発地から目的地までの最短距離をsDistに、最短経路上の地点の地点番号を目的地から出発地までの順に配列sRouteに設定する。