解説

〔アについて〕
表1の5回目では、終点であるV5が更新起点ノードとなり、始点ノードV1から終点ノードV5までの最短距離が確定しています。<>内の数値は、当該ノードの始点ノード距離を示すため、空欄アには始点ノードV1から終点ノードV5までの最短距離が入るはずです。図1を見ると、V1からV5までの最短距離は「V1→V2→V4→V5」で「10＋4＋3＝17」なので、空欄aには「17」が当てはまります。

表1で終点ノードが確定するまでの手順を説明すると以下のようになります。

【1回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV1<0>なので、V1までの最短距離が0で確定する。V1を更新起点ノードとして、隣接するV2、V3の始点距離ノードを計算すると、V1→V2が10、V1→V3が16なので、V2<10>、V3<16>のままとなる（更新なし）。

【2回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV2<10>なので、V2までの最短距離が10で確定する。V2を更新起点ノードとして、隣接するV3、V4の始点距離ノードを計算すると、V2→V3が14、V2→V4が13なので、V3<14>、V4は<13>で更新される。

【3回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV4<13>なので、V4までの最短距離が13で確定する。V4を更新起点ノードとして、隣接するV3、V5の始点距離ノードを計算すると、V4→V3が15、V4→V5が19なので、V5は<19>で更新される。

【4回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV3<14>なので、V3までの最短距離が14で確定する。V3を更新起点ノードとして、隣接するV5の始点距離ノードを計算すると、V3→V5が17なので、V5は<17>で更新される。

【5回目】
最短距離が確定していないノードの中で、始点ノード距離が最小のノードはV5<17>なので、V5までの最短距離が17で確定する。V5は終点なので処理が終了する。

∴ア＝17

解説

〔始点から終点までの最短距離を求める手順（以下、手順という）〕の①～③と〔最短距離の算出プログラム〕とは次のように対応しています。〔イウについて〕
2つの空欄は、手順①の更新起点ノードを選ぶ処理に関連しています。

14～19行目のfor文では次の処理を行っています。

1. 1からN（ノード1からノードN）まで繰り返す
2. if文がtrueであれば minDist と curNode を設定する

上記ⅱで設定される変数 curNode は更新起点ノードを表します。手順①より、更新起点ノードとは「最短距離が確定していないノードの中で，始点ノード距離が最小のノード」ですから、curNode を変更する必要があるのは、次の2つの条件をともに満たすノードが見つかったときです。

• 最短距離が確定していない
• 始点ノード距離が現在の最短距離よりも小さい

この2つがif文の条件式になります。if文の条件式のうちdone[k]が0は、7行目コメントより「ノードkの最短距離が確定していない」ことを表しています。したがって、空欄イにはもうひとつの条件である「始点ノード距離が現在の最短距離よりも小さい」であることを表す式が入ると判断できます。

現在のノードの始点ノード距離は、6行目コメントより dist[k] で参照することができます。現在の最短距離は、その名称と使われ方より変数 minDist に保持されていると考えられるので、dist[k] と minDist を比較することになります。したがって、空欄イには dist[k]がminDistより小さい が当てはまります。

次に空欄ウについて考えます。
if文がtrueとなり curNode が変更される場合、その後の比較のために、そのノードの始点ノード距離を現在の最短距離として保持しておく必要があります。前述のとおり、現在の最短距離を保持する変数が minDist なので、minDist には「現在のノードの始点ノード距離」を格納することになります。したがって、空欄ウには dist[k] が当てはまります。

∴イ＝dist[k]がminDistより小さい
　ウ＝dist[k]

〔エについて〕
空欄は、手順③の始点ノード距離を更新する処理に関連しています。

24～28行目のfor文では次の処理を行っています。

1. 1からN（ノード1からノードN）まで繰り返す
2. if文がtrueであれば dist[k] を設定する

上記ⅱで設定される変数 dist[k] は現在のノードの始点ノード距離を表します。手順③より、始点ノード距離を更新するのは、最短距離が確定していないノードであり、更新起点ノードを経由した場合の始点ノード距離が、現在の始点ノード距離よりも小さい場合ですから、dist[k] を変更する必要があるのは、次の2つの条件をともに満たすノードが見つかったときです。

• 最短距離が確定していない
• 更新起点ノードを経由した場合の始点ノード距離が、現在の始点ノード距離よりも小さい

25行目のif文の条件のうちdone[k]が0は、「ノードkの最短距離が確定していない」を表します。したがって空欄エのほうの条件式では、「更新起点ノードを経由した場合の始点ノード距離が、現在の始点ノード距離よりも小さい」という条件判定を行うことになります。条件後半の「現在の始点ノード距離よりも小さい」は、空欄エの後ろのdist[k]より小さいに対応するので、空欄エには「更新起点ノードを経由した場合の始点ノード距離」を表す式が入ると判断できます。

更新起点ノードを経由した場合の始点ノード距離は、次の2つの合計値として求めることができます。

• 更新起点ノードの始点ノード距離　dist[curNode]
• 更新起点ノードから現在のノードまでの距離　edge[curNode, k]

したがって、空欄エには dist[curNode]＋edge[curNode, k] が当てはまります。

なお、現在の更新起点ノードの始点ノード距離は、手順①の処理で minDist に格納されたままになっているので、dist[curNode] を minDist に変えても正しく動作します。

∴エ＝dist[curNode] ＋ edge[curNode, k]

解説

〔キについて〕
「キを選ぶ回数は，一度選ばれると当該ノードの最短距離は確定するので…」とあるので、最短距離が確定するときに選ばれるものを考えます。手順①には「始点ノード距離が最小のノードを更新起点ノードとして選び，そのときの始点ノード距離の値で，当該更新起点ノードの最短距離を確定する」とあるため、これに該当するのは「更新起点ノード」であることがわかります。

∴キ＝更新起点ノード

〔クについて〕
〔計算量の考察〕には「次の【キ：更新起点ノード】を選ぶために始点ノード距離を計算する回数は最大でもN回である」とあります。これは手順③に対応します。手順③は最大でN回実行されるため、計算量（オーダ）はO(N)です。同様に、手順①も最大でN回実行されるfor文を含むので、計算量はO(N)です。手順②は繰返し処理がないのでO(1)です。以上より、手順①～③を1回実行した場合の計算量は、O(N)＋O(1)＋O(N) ⇒ O(N) となります（オーダ記法では定数は無視します）。

また「【キ：更新起点ノード】を選ぶ回数は，一度選ばれると当該ノードの最短距離は確定するので，最大でもN回である」とあります。これは、更新起点ノードを1つ選ぶごとに1回実行されるwhile文の繰返しに対応します。while文は最大でN回実行されるため、計算量はO(N)です。

関数 distance のプログラムは、while文の中に2つのfor文が含まれる構造をしています。最大でN回繰り返すwhile文の中に、最大でN回繰り返すfor文があるため、このプログラムのオーダは O(N)×O(N) ⇒ O(N²) になります。したがって、空欄クには「N²」が入ります。

∴ク＝N²