応用情報技術者 2024年 春期 午後 問03

　グラフ内の二つのノード間の最短経路を求めるアルゴリズムにダイクストラ法がある。このアルゴリズムは、車載ナビゲーションシステムなどに採用されている。 　 〔経路算定のモデル化〕 　グラフは、有限個のノードの集合と、その中の二つのノードを結ぶエッジの集合とから成る数理モデルである。ダイクストラ法による最短経路の探索問題を考えるに当たり、本問では、エッジをどちらの方向にも行き来することができ、任意の二つのノード間に経路が存在するグラフを扱う。ここで、グラフを次のように定義する。 　・ノードの個数を N とし、N は 2 以上とする。ノードの番号 (以下、ノード番号という) は、始点のノード番号を 1 とし、1 から始まる連続した整数とする。ノードには、ノード番号に対応させて、V1, V2, V3, …、VN とラベルを付ける。 　・二つのノードが他のノードを経由せずにエッジでつながっているとき、それらのノードは隣接するという。隣接するノード間のエッジには、ノード間の距離として正の数値を付ける。 　・始点のノード (以下、始点という) と別のノードを終点のノード (以下、終点という) として定める。始点からあるノードまでの経路の中から、経路に含まれるエッジに付けられた距離の和が最小の距離を最短距離といい、始点から終点までの最短距離となる経路を最短経路という。 　　図1にノードが五つのグラフの例を示す。図1の例では、始点を V1 のノードとし、終点を V5 のノードとした場合の最短経路は、V1, V2, V3, V5 のノードを順にたどる経路である。

〔始点から終点までの最短距離を求める手順〕 　ダイクストラ法による始点から終点までの最短距離の算出は次のように行う。 　最初に、各ノードについて、始点からそのノードまでの距離（以下、始点ノード距離という）を作業用に導入して十分に大きい定数としておく。ただし、始点の始点ノード距離は0とする。この時点では、どのノードの最短距離も確定していない。 　次に、終点の最短距離が確定するまで、①〜③を繰り返す。ここで、始点との距離を算出する基準となるノードを更新起点ノードという。 　① 最短距離が確定していないノードの中で、始点ノード距離が最小のノードを更新起点ノードとして選び、そのときの始点ノード距離の値で、当該更新起点ノードの最短距離を確定する。更新起点ノードを選ぶ際に、始点ノード距離が最小となるノードが複数ある場合は、その中の任意のノードを更新起点ノードとして選ぶ。 　② 更新起点ノードが終点であれば、終了する。 　③ ①で選択した更新起点ノードに隣接しており、かつ、最短距離が確定していない全てのノードについて、更新起点ノードを経由した場合の始点ノード距離を計算する。ここで計算した始点ノード距離が、そのノードの現在までの始点ノード距離よりも小さい場合には、そのノードの現在までの始点ノード距離を更新する。 　 〔図1の例における最短距離を求める手順と始点ノード距離〕 　図1の例において、始点V1から終点V5までの経路に対して、上の①〜③を繰り返し適用する。そのとき、更新起点ノードを選ぶたびに、更新起点ノードの始点ノード距離、更新起点ノードと隣接するノードの始点ノード距離、及び最短距離が確定していないノードの始点ノード距離を計算した内容を表1に示す。

〔最短距離の算出プログラム〕 　始点から終点までの最短距離を求める関数 distance のプログラムを図2に示す。 　配列の要素番号は 1 から始まるものとする。また、行頭の数字は行番号を表す。

〔最短経路の出力〕 　関数 distance を変更して、求めた最短距離となる最短経路を出力できるようにする。具体的には、まず、ノード番号1〜nを格納する配列 viaNode を使用するために、図3の変数宣言を図2の行10の直後に、図4のプログラムを図2の行21の直後に、それぞれ挿入する。さらに、各ノードの始点ノード距離を更新するたびに、直前に経由したノード番号を viaNode に格納する①代入文を一つ、図2のプログラムの行オの直後に挿入する。 　このプログラムの変更によって、終点のノード番号を起点として カ などとすることで、最短経路のノード番号を逆順に出力する。

〔計算量の考察〕 　関数 distance では、次の キ を選ぶために始点ノード距離を計算する回数は最大でも N 回である。また、キ を選ぶ回数は、一度選ばれると当該ノードの最短距離は確定するので、最大でも N 回である。よって、最悪の場合の計算量は、O(ク) である。