基本情報技術者 2012年 秋期 午後 問08

　鉄道の路線がある。駅数Nは2以上で、各駅には駅番号（1, 2, …, N）が付いている。どの任意の2駅間にも、それらを結ぶ経路が一つ以上存在する。また、隣接する2駅間を直接結ぶ経路は一つだけ存在し、その距離が与えられている。図1に5駅からなる鉄道の路線例を示す。

　 〔プログラムの説明〕 　副プログラムCalcDistは、駅数N及び要素数N×Nの2次元配列Distを受け取り、プログラムに示すアルゴリズム（Warshall-Floyd法）によって、配列Distの内容を更新しながら各駅間の最短距離を求めていく。実行が終わると、任意の2駅i, j間の最短距離がDist[i][j]に求められている。どの2駅についても、その最短距離は999より小さいものとする。配列Distの添字は1から始まる。 　副プログラムCalcDistに渡す配列Distには、次の値を格納する。なお、図1の路線情報を格納した配列Distの内容を、図2の初期値に示してある。 (1) 2駅i, jが隣接しているとき、Dist[i][j]及びDist[j][i]には、その駅間距離を格納する。例えば、図1の駅①と②は隣接しているので、Dist[1][2]及びDist[2][1]には、18を格納する。 (2) 2駅i, jが隣接していないとき、Dist[i][j]及びDist[j][i]には、未確定を表す距離999を格納する。例えば、図1の駅①と③は隣接していないので、Dist[1][3]及びDist[3][1]には、999を格納する。 (3) 各駅iについて、Dist[i][i]には0を格納する。 　副プログラムCalcDist中のPrint(N, Dist)は、配列Distのその時点の内容を印字する副プログラムである。

　図1の路線情報を配列Distに格納して、CalcDistを実行した。配列Distの内容の変化をPrint(N, Dist)で印字した結果は、図2のとおりであった。

　駅数Nに関して、副プログラムCalcDistの計算量のオーダはc、またメモリ使用量のオーダはdである。そこで、駅数Nが大きい場合に、計算量やメモリ使用量を減らすための方法を考える。 　例えば、配列Distの対称性に着目し、プログラム中の破線で囲んだ部分を、

とすれば、繰返し処理中の選択処理の実行回数を約半分に減らすことができる。 　次に、少ないメモリ使用量で、任意の2駅i, j間の最短距離を求める方法を考える。 　駅を、乗換駅（3方向以上に隣接する駅がある）、終端駅（1方向だけに隣接する駅がある）、中間駅（2方向だけに隣接する駅がある）の3種類に分ける。乗換駅と終端駅を合わせて基幹駅と呼ぶ。基幹駅の数をKとして、駅番号1～Kが基幹駅、駅番号K+1～Nが中間駅となるように駅番号を定める。ここで、K≧2であるとする。図3の路線例では、駅①～③が乗換駅、駅④が終端駅、駅⑤～⑩が中間駅である。

　各駅間の最短距離は、次の方法で求める。 (1) 中間駅を全て除いて、基幹駅だけからなる路線を考え、二つの基幹駅を結ぶ経路ごとに一意の区間名を付ける。図3の路線例にこの操作を加えたものが図4である。例えば、図3の経路①－⑤－⑥－③は、図4の区間Bに対応する。

(2) 要素数K×Kの2次元配列Distを用意し、事前に配列Distに各基幹駅間の最短距離を求めておく。 (3) 全ての駅について、表1に示す形式の駅情報表を用意する（表1には、図3の駅情報の一部が示してある）。 　中間駅の場合、Secはその駅が属する区間の区間名、KL, KHはその駅が属する区間の両端の駅番号（KL≦KHとする）、ToKL, ToKHはその駅から駅KL, KHまでの距離である。基幹駅の場合、その駅は自分自身の駅を両端とする距離0の区間に属すると考えて、表1の例のように中間駅と同様の情報を用意する。 　これらの情報は、駅番号を添字として参照する。例えば、駅番号5のToKLの値はToKL[5]として参照する。

(4) 2駅i, j間の最短距離を求める。一般に、両駅が属する区間が異なる場合、駅iから駅jへ行く経路は、 　　（駅i）→（駅iが属する区間のいずれか一端の基幹駅） 　　　→（駅jが属する区間のいずれか一端の基幹駅）→（駅j） となる。したがって、次の式で求める4通りの値D1, D2, D3, D4のうちの最小値が、2駅i, j間の最短距離となる。 　 　・D1 ← ToKL[i] + Dist[KL[i]][KL[j]] + ToKL[j] 　・D2 ← ToKL[i] + Dist[KL[i]][KH[j]] + ToKH[j] 　・D3 ← ToKH[i] + Dist[KH[i]][KL[j]] + ToKL[j] 　・D4 ← ToKH[i] + Dist[KH[i]][KH[j]] + ToKH[j] 　 　両駅が属する区間が同じ場合は、区間の端の基幹駅を経由せずに直接駅iから駅jへ行く経路がある。これも考慮すると、任意の2駅i, j間の最短距離Resは次の処理で求められる。ここで、関数min(式1, 式2, …)は、式1, 式2, …の値の最小値を返す関数であり、関数abs(式)は、式の値の絶対値を返す関数である。

　この方法なら、2次元配列Distの要素数をN×NからK×Kに削減できる。ただし、表1に示す表が増えるので、例えばK=5のとき、配列及び表が占めるメモリ使用量を削減できるのはN≧gの場合となる。ここで、表1に示す表は、1駅について配列Distの要素5個分のメモリを使用するものとする。