基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

a，bが含まれるプログラム23～29行目の処理は本文中で次のように説明されています。

「出発地点からの最短距離が未確定の地点の中で，出発地からの距離が最も近い地点を探し，その地点を sPoint とし，その地点の最短距離を確定する」

〔aについて〕

aは分岐条件式の一部で、上記の処理のうち「出発地点からの最短距離が未確定の地点」を絞る部分になります。
各地点の確定状況は配列変数 pFixed に格納されています。pFixed の要素はfalseで初期化されていますが、ある地点の最短距離が確定すると、その地点に対応する配列要素の値がtrueになります。例えば、地点2が確定すれば pFixed[1]がtrueになり、地点6が確定すれば pFixed[5] がtrueになるといった具合です。つまり、最短距離が未確定の地点では、その地点に対応する pFixed の値がfalseのままになっているはずです。

aが含まれるループでは、ループ変数 j を0から地点数-1まで増やしながら、すべての地点を対象に処理を行っています。このループ内ではループ変数 j が現在処理対象の地点番号を示しているため、その地点が確定しているかどうかを確認するには pFixed[j] の値を参照すればよいことになります。前述のとおり、未確定であれば　pFixed[j]=false になっているはずなので、aには pFixed[j]=false のときに真となる条件式、すなわち not(pFixed[j]) が入ります。

∴a＝イ：not(pFixed[j])

〔bについて〕
aが含まれるループ内では、本文中に記載されている通り「未確定の地点の中で，最短距離がより短い地点を探す」処理が行われます。
ループ内では、pDist[j]とpDist[i]を比較し、pDist[j]のほうが小さければ、iにjを代入するという処理を繰り返しています。この処理により、iには pDist の要素のうち未確定かつ最も値が小さい要素の添字が格納されることになります。例えば pDist=[0,5,4,∞,∞,8,∞]であり、地点0が確定済であったならば、ループを抜けた後のiには2が格納されているといった具合です。

プログラムの説明にあるように、最も近い地点を探した後は、「その地点を sPoint とし，その地点の最短距離を確定」します。つまり、28行目の以下の処理が sPoint に最も近い地点番号(i)を設定する処理になります。
そして、その地点の最短距離を確定します。最短距離の確定は、pFixed の対応する要素をtrueにすることで行いますが、確定する地点番号は sPoint に格納されているので、pFixed[sPoint] の値をtrueにすることになります。
∴b＝オ：sPoint

c，dが含まれるプログラム40～48行目の処理は本文中で次のように説明されています。

「出発地から目的地までの最短距離を sDist に，最短経路上の地点の地点番号を目的地から出発地までの順に配列 sRoute に設定する」

40行目に以下の処理がありますが、
この部分が sDist に最短距離を設定する処理なので、地点番号を sRoute に設定しているのは41行目以降になります。

〔cについて〕
cに対しては次の2つの部分で値の設定が行われています。
ループの開始時にiがdpで初期化されていることから、cには目的地の地点番号(dp)および出発地の地点番号(sp)を設定していることになります。このことからcは、配列変数 sRoute であるとわかります。
次に sRoute の添え字について考えます。sRoute には配列の先頭から順に経由地の地点番号が設定されることになっています。つまり最初に設定されるのがsRoute[0]、その次がsRoute[1]、…ということになります。したがって初期値が0であり、ループを重ねるたびに1ずつ加算されているjを添え字に用いるのが適切です。

∴c＝キ：sRoute[j]

〔dについて〕
sRoute には目的地→経由地→出発地の順で地点番号が設定されます。ある地点における直前の経由地の地点番号は pRoute に格納されているので、これを参照することになります。プログラム上では、sRoute[j] に設定される地点番号は変数iが保持しているので、次に設定すべき経由地番号は pRoute[i] を参照することで得られます。

つまり、以下のように ①sRoute[j]に経由地を追加、②その地点の直前の経由地番号をiに設定 という操作を繰り返すことで、目的地から出発地までに経由する地点番号を列挙できます。
したがってdには pRoute[i] が入ります。

∴d＝イ：pRoute[i]

例えば pRoute=[0,0,4,0,1,2,5]、sp=0、dp=6 であれば、プログラムは次のように動作します。

1回目から3回目までプログラムをトレースしていくと次のようになります。

[1回目]
pFixed=[false,false,false,false,false,false,false]
pDist=[0,∞,∞,∞,∞,∞,∞]
pRoute=[0,0,0,0,0,0,0]

最初に登場する14～19行目の処理では、pFixed を最初から参照していき、値がfalseの要素が見つかった時点でループを抜けます。
1回目では pFixed の最初の要素である pFixed[0] がfalseなので、ループ終了時のiには0が格納されます。このときすべての地点が確定していればループ後のiの値が nPoint になり、最短経路探索処理が終了することになります（20～22行目）。しかし1回目のループでは i = nPoint が偽なので後続の処理に移ります。

続く23～27行目の処理では、pDist のうち未確定かつ最も小さい要素を探します。
1回目の時点では pDist[0] 以外は∞であり、pDist[j] ＜ pDist[i] が真になることはない（i ← j の処理が行われることない）ので、ループを抜けた後のiには0が格納されたままです。

続く28～29行目の処理ではsPointにiを代入し、pFixed[sPoint]を確定します。
この時点で、pFixed[0]にtrueが代入され地点0への最短距離が確定します。出発地＝地点0なので、当然のことながら最短距離は0です。

　pFixed=[true,false,false,false,false,false,false]

続く30～39行目までのループでは、sPointの隣接地点のうち未確定の地点に対して現時点での最短距離を更新しています。地点0に隣接しているのは地点1、地点2、地点3なので、対応する pDist と pRoute の各要素が更新されます。具体的には、pDist[1]にはDistance[0][1]の2、pDist[2]にはDistance[0][2]の8、pDist[3]にはDistance[0][3]の4が格納されます。また直前の経由地情報を格納する pRouteの各要素には sPoint の0が格納されます。pDist=[0,2,8,4,∞,∞,∞]
pRoute=[0,0,0,0,0,0,0]

[2回目]
pFixed=[true,false,false,false,false,false,false]
pDist=[0,2,8,4,∞,∞,∞]
pRoute=[0,0,0,0,0,0,0]

まず14～22行目の処理ですが、pFixed[1]がfalseなのでループを抜けた後のiは1になります。i = sPoint が偽なので続く処理に移ります。
23～27行目の処理処理では、pDist のうち未確定かつ最も小さい要素を探します。pDist[1]=2 がそれに当たるためループ終了時のiには1が格納されます。
28～29行目では、sPointに1が格納されるとともに、pFixed[1]にtrueが代入され、地点1への最短距離が確定します。

　pFixed=[true,true,false,false,false,false,false]

続く30～39行目までのループでは、未確定かつ地点1に隣接している地点4に対応するpDist[4]とpRoute[4]の各要素が更新されます。具体的には、pDist[4]には地点1への最短距離である"pDist[1]"に地点1→地点4までの距離"Distance[1][4]"を加えた5、pRoute[4]には直前の経由地となる1が格納されます。
pDist=[0,2,8,4,5,∞,∞]
pRoute=[0,0,0,0,1,0,0][3回目]
さて、ここからが　に関係する3回目の処理です。この時点で pDist とpRoute は設問の表3と同じ状態になっています。

pFixed=[true,true,false,false,false,false,false]
pDist=[0,2,8,4,5,∞,∞]
pRoute=[0,0,0,0,1,0,0]

まず14～22行目の処理ですが、pFixed[2]がfalseなのでループを抜けた後のiは2になります。i = sPoint が偽なので続く処理に移ります。
23～27行目の処理処理では、pDist のうち未確定かつ最も小さい要素を探します。pDist[3]=4 がそれに当たるためループ終了時のiには3が格納されます。
28～29行目では、sPointに3が格納されるとともに、pFixed[3]にtrueが代入され地点3への最短距離が確定します。つまりe＝3が適切です。

　pFixed=[true,true,false,true,false,false,false]

続く30～39行目までのループでは、未確定かつ地点3に隣接している地点5に対応するpDist[5]とpRoute[5]の各要素が更新されます。具体的には、pDist[5]にはpDist[3]の値にDistance[3][5]を加えた12、pRoute[5]には直前の経由地となる3が格納されます。
pDist=[0,2,8,4,5,12,∞]
pRoute=[0,0,0,0,1,3,0]

したがって、ループ3回目終了時点における pDist[] の状態は[0,2,8,4,5,12,∞]、pRoute[] の状態は[0,0,0,0,1,3,0]になります。

∴e＝イ：3
　f＝カ：0,2,8,4,5,12,∞
　g＝ア：0,0,0,0,1,3,0

最後になりますが、以下に本アルゴリズムをJavaScriptで実装したものを掲載しますので細かな動きの確認などにご使用ください。