2024年 春期 応用情報技術者試験 問3

グラフのノード間の最短経路を求めるアルゴリズム

グラフ内の二つのノード間の最短経路を求めるアルゴリズムにダイクストラ法がある。このアルゴリズムは、車載ナビゲーションシステムなどに採用されている。

【経路算定のモデル化】

グラフは、有限個のノードの集合と、その中の二つのノードを結ぶエッジの集合とから成る数理モデルである。ダイクストラ法による最短経路の探索問題を考えるに当たり、本問では、エッジをどちらの方向にも行き来することができ、任意の二つのノード間に経路が存在するグラフを扱う。ここで、グラフを次のように定義する。

・ノードの個数を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から始まるものとする。また、行頭の数字は行の番号を表す。

1: ○整数型: distance()
2:     整数型: N                    /* ノードの個数 */
3:     整数型: INF                  /* 十分大きい定数 */
4:     整数型の二次元配列: edge      /* edge[m, n]には、ノードmからノードnへの距離を格納
                                      二つのノードが隣接していない場合はINFを格納 */
5:     整数型: GOAL                 /* 終点のノード番号 */
6:     整数型の配列: dist           /* 始点ノード距離、初期値はINF、要素番号がノード番号を表す。 */
7:     整数型の配列: done           /* 最短距離が確定したら1を入れる。
                                      要素番号がノード番号を表す。 */
8:     整数型: curNode              /* 更新起点ノードのノード番号 */
9:     整数型: minDist              /* 更新起点ノードを求める際に使用する一時変数 */
10:    整数型: k                    /* 要素番号 */
11:    dist[1] ← 0                  /* 始点の始点ノード距離を0とする。 */
12:    while (true)
13:        minDist ← INF
14:        for (kを1からNまで1ずつ増やす)
15:            if (done[k]が0 かつ イ )
16:                minDist ← ウ
17:                curNode ← k
18:            endif
19:        endfor
20:        done[curNode] ← 1
21:        if (curNode が GOAL と等しい)
22:            return dist[curNode]
23:        endif
24:        for (kを1からNまで1ずつ増やす)
25:            if ( エ が dist[k] より小さい かつ done[k]が0)
26:                dist[k] ← エ
27:            endif
28:        endfor
29:    endwhile

【最短経路の出力】

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

このプログラムの変更によって、終点のノード番号を起点としてカなどすることで、最短経路のノード番号を逆順に出力する。

整数型の配列: viaNode        /* 最短経路のノード番号を格納する。初期値は0。 */
整数型: j                    /* 要素番号 */
図3　最短経路を出力するために関数distanceに挿入する変数宣言

j ← GOAL                     /* 終点のノード番号 */
GOALを出力                   /* 終点のノード番号の出力 */
while (j が 1 より大きい)    /* 最短経路の出力 */
    viaNode[j]を出力
    j ← viaNode[j]
endwhile

【計算量の考察】

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