グラフのノード間の最短経路を求めるアルゴリズムに関する次の記述を読んで設問に答えよ。
グラフ内の二つのノード間の最短経路を求めるアルゴリズムにダイクストラ法がある。このアルゴリズムは，車載ナビゲーションシステムなどに採用されている。
〔経路算定のモデル化〕
グラフは，有限個のノードの集合と，その中の二つのノードを結ぶエッジの集合とから成る数理モデルである。ダイクストラ法による最短経路の探索問題を考えるに当たり，本間では，エッジをどちらの方向にも行き来することができ，任意の二つのノード間に経路が存在するグラフを扱う。ここで，グラフを次のように定義する。
・ノードの個数をNとし，Nは2以上とする。ノードの番号（以下，ノード番号という）は，始点のノード番号を1とし，1から始まる連続した整数とする。ノードには，ノード番号に対応させて，V1，V2，V3，…，VNとラベルを付ける。
・二つのノードが他のノードを経由せずにエッジでつながっているとき，それらのノードは隣接するという。隣接するノード間のエッジには，ノード間の距離として正の数値を付ける。
・始点のノード（以下，始点という）とは別のノードを終点のノード（以下，終点という）として定める。始点からあるノードまでの経路の中から，経路に含まれるエッジに付けられた距離の和が最小の距離を最短距離という。始点から終点までの最短距離となる経路を最短経路という。
図1にノードが五つのグラフの例を示す。図1の例では，始点をV1のノードとし，終点をV5のノードとした場合の最短経路は，V1，V2，V3，V5のノードを順にたどる経路である。
図1 ノードが五つのグラフの例
〔始点から終点までの最短距離を求める手順〕
ダイクストラ法による始点から終点までの最短距離の算出は次のように行う。
最初に，各ノードについて，始点からそのノードまでの距離（以下，始点ノード距離という）を作業用に導入して十分に大きい定数としておく。ただし，始点の始点ノード距離は0とする。この時点では，どのノードの最短距離も確定していない。
次に，終点の最短距離が確定するまで，①〜③を繰り返す。ここで，始点との距離を算出する基準となるノードを更新起点ノードという。
① 最短距離が確定していないノードの中で，始点ノード距離が最小のノードを更新起点ノードとして選び，そのときの始点ノード距離の値で，当該更新起点ノードの最短距離を確定する。更新起点ノードを選ぶ際に，始点ノード距離が最小となるノードが複数ある場合は，その中の任意のノードを更新起点ノードとして選ぶ。
② 更新起点ノードが終点であれば，終了する。
③ ①で選択した更新起点ノードに隣接しており，かつ，最短距離が確定していない全てのノードについて，更新起点ノードを経由した場合の始点ノード距離を計算する。ここで計算した始点ノード距離が，そのノードの現在までの始点ノード距離よりも小さい場合には，そのノードの現在までの始点ノード距離を更新する。
〔図1の例における最短距離を求める手順と始点ノード距離〕
図1の例において，始点V1から終点V5までの経路に対して，上の①〜③を繰返し適用する。そのとき，更新起点ノードを選ぶたびに，更新起点ノードの始点ノード距離更新起点ノードと隣接するノードの始点ノード距離，及び最短距離が確定していないノードの始点ノード距離を計算した内容を表1に示す。
表1 図1の例における最短距離を求める手順と始点ノード距離
〔最短距離の算出プログラム〕
始点から終点までの最短距離を求める関数distanceのプログラムを図2に示す。配列の要素番号は1から始まるものとする。また，行頭の数字は行の番号を表す。
図2 関数distanceのプログラム
〔最短経路の出力〕
関数distanceを変更して，求めた最短距離となる最短経路を出力できるようにする。具体的には，まず，ノード番号1〜Nを格納する配列viaNodeを使用するために，図3の変数宣言を図2の行10の直後に，図4のプログラムを図2の行21の直後に，それぞれ挿入する。さらに，各ノードの始点ノード距離を更新するたびに，直前に経由したノード番号をviaNodeに格納する①代入文を一つ，図2のプログラムの行 オ の直後に挿入する。
このプログラムの変更によって，終点のノード番号を起点として カ たどることで，最短経路のノード番号を逆順に出力する。
図3 最短経路を出力するために関数distanceに挿入する変数宣言
図4 最短経路を出力するために関数distanceに挿入するプログラム
〔計算量の考察〕
関数distanceでは，次の キ を選ぶために始点ノード距離を計算する回数は最大でもN回である。また， キ を選ぶ回数は，一度選ばれると当該ノードの最短距離は確定するので，最大でもN回である。よって，最悪の場合の計算量は，O（ ク ）である。
設問1 表1中の ア に入れる適切な字句を答えよ。
解答・解説
解答例
17
解説
ー
設問2 図2中の イ 〜 エ に入れる適切な字句を答えよ。
解答・解説
解答例
イ：dist[k] < minDist
ウ：dist[k]
エ：dist[curNode] + edge[curNode, k]
解説
ー
設問3 〔最短経路の出力〕について答えよ。
（1）本文中の下線①と オ について，挿入すべき代入文と オ に入れる行の番号を答えよ。行の番号については，最も小さい番号を答えること。ただし，図2中の現在の行の番号は図3及び図4の挿入によって変化しないものとする。
解答・解説
解答例
代入文：viaNode[k] <- curNode
行番号：25
解説
ー
（2）本文中の カ に入れる適切な字句を解答群の中から選び，記号で答えよ。
- viaNodeに格納してあるノード番号を
- viaNodeの要素番号を大きい方から
- viaNodeの要素番号を小さい方から
解答・解説
解答例
ア
解説
ー
設問4 〔計算量の考察〕について答えよ。
（1）本文中の キ に入れる適切な字句を，本文中の字句を用いて10字以内で答えよ。
解答・解説
解答例
更新起点ノード
解説
ー
（2）本文中の ク に入れる適切な字句を答えよ。
解答・解説
解答例
N²
解説
ー
IPA公開情報
出題趣旨
（公開前）
採点講評
（公開前）
