問題プレビューID: da7f44c9応用情報技術者試験 2024年(令和6年度)春期 午後
グラフのノード間の最短経路を求めるアルゴリズムに関する次の記述を読んで,設問に答えよ。
グラフ内の二つのノード間の最短経路を求めるアルゴリズムにダイクストラ法がある。このアルゴリズムは,車載ナビゲーションシステムなどに採用されている。
〔経路算定のモデル化〕
グラフは,有限個のノードの集合と,その中の二つのノードを結ぶエッジの集合とから成る数理モデルである。ダイクストラ法による最短経路の探索問題を考えるに当たり,本問では,エッジをどちらの方向にも行き来することができ,任意の二つのノード間に経路が存在するグラフを扱う。ここで,グラフを次のように定義する。
- ノードの個数を N とし,N は 2 以上とする。ノードの番号(以下,ノード番号という)は,始点のノード番号を 1 とし,1 から始まる連続した整数とする。ノードには,ノード番号に対応させて,V1,V2,V3,…,VN とラベルを付ける。
- 二つのノードが他のノードを経由せずにエッジでつながっているとき,それらのノードは隣接するという。隣接するノード間のエッジには,ノード間の距離として正の数値を付ける。
- 始点のノード(以下,始点という)とは別のノードを終点のノード(以下,終点という)として定める。始点からあるノードまでの経路の中から,経路に含まれるエッジに付けられた距離の和が最小の距離を最短距離という。始点から終点までの最短距離となる経路を最短経路という。
図 1 にノードが五つのグラフの例を示す。図 1 の例では,始点を V1 のノードとし,終点を V5 のノードとした場合の最短経路は,V1,V2,V3,V5 のノードを順にたどる経路である。
図 1 ノードが五つのグラフの例
V1-V2 間の距離は 10,V2-V4 間は 3,V4-V5 間は 6,V2-V3 間は 4,V4-V3 間は 2,V3-V5 間は 3,V1-V3 間は 16 である。
〔始点から終点までの最短距離を求める手順〕
ダイクストラ法による始点から終点までの最短距離の算出は次のように行う。
最初に,各ノードについて,始点からそのノードまでの距離(以下,始点ノード距離という)を作業用に導入して十分に大きい定数としておく。ただし,始点の始点ノード距離は 0 とする。この時点では,どのノードの最短距離も確定していない。
次に,終点の最短距離が確定するまで,①~③を繰り返す。ここで,始点との距離を算出する基準となるノードを更新起点ノードという。
① 最短距離が確定していないノードの中で,始点ノード距離が最小のノードを更新起点ノードとして選び,そのときの始点ノード距離の値で,当該更新起点ノードの最短距離を確定する。更新起点ノードを選ぶ際に,始点ノード距離が最小となるノードが複数ある場合は,その中の任意のノードを更新起点ノードとして選ぶ。
② 更新起点ノードが終点であれば,終了する。
③ ①で選択した更新起点ノードに隣接しており,かつ,最短距離が確定していない全てのノードについて,更新起点ノードを経由した場合の始点ノード距離を計算する。ここで計算した始点ノード距離が,そのノードの現在までの始点ノード距離よりも小さい場合には,そのノードの現在までの始点ノード距離を更新する。
〔図 1 の例における最短距離を求める手順と始点ノード距離〕
図 1 の例において,始点 V1 から終点 V5 までの経路に対して,上の①~③を繰り返し適用する。そのとき,更新起点ノードを選ぶたびに,更新起点ノードの始点ノード距離,更新起点ノードと隣接するノードの始点ノード距離,及び最短距離が確定していないノードの始点ノード距離を計算した内容を表 1 に示す。
表 1 図 1 の例における最短距離を求める手順と始点ノード距離
| 探索適用回数 | 更新起点ノード | 最短距離が確定していない,更新起点ノードに隣接するノード | 最短距離が確定していないノード |
|---|---|---|---|
| 1 回目 | V1 <0> | V2 <10>,V3 <16> | V2 <10>,V3 <16>,V4 <INF>,V5 <INF> |
| 2 回目 | V2 <10> | V3 <14>,V4 <13> | V3 <14>,V4 <13>,V5 <INF> |
| 3 回目 | V4 <13> | V3 <14>,V5 <19> | V3 <14>,V5 <19> |
| 4 回目 | V3 <14> | V5 <[ア]> | V5 <[ア]> |
| 5 回目 | V5 <[ア]> | - | - |
注記 1 INF は,定数で十分大きい数を表す。
注記 2 <>内の数値は,当該ノードの始点ノード距離を表す。
〔最短距離の算出プログラム〕
始点から終点までの最短距離を求める関数 distance のプログラムを図 2 に示す。配列の要素番号は 1 から始まるものとする。また,行頭の数字は行の番号を表す。
図 2 関数 distance のプログラム
1: ○整数型: distance()
2: 整数型: N /* ノードの個数 */
3: 整数型: INF /* 十分大きい定数 */
4: 整数型の二次元配列: edge /* edge[m, n]には,ノードmからノードnへの距離を格納
二つのノードが隣接していない場合には INF を格納 */
5: 整数型: GOAL /* 終点のノード番号 */
6: 整数型の配列: dist /* 始点ノード距離。初期値は INF。要素番号がノード番号を表す。 */
7: 整数型の配列: done /* 初期値は 0。最短距離が確定したら 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 のプログラムの行[オ]の直後に挿入する。
このプログラムの変更によって,終点のノード番号を起点として[カ]たどることで,最短経路のノード番号を逆順に出力する。
図 3 最短経路を出力するために関数 distance に挿入する変数宣言
整数型の配列: viaNode /* 最短経路のノード番号を格納する。初期値は 0。 */
整数型: j /* 要素番号 */
図 4 最短経路を出力するために関数 distance に挿入するプログラム
j ← GOAL /* 終点のノード番号 */
GOAL を出力 /* 終点のノード番号の出力 */
while (j が 1 より大きい) /* 最短経路の出力 */
viaNode[j]を出力
j ← viaNode[j]
endwhile
〔計算量の考察〕
関数 distance では,次の[キ]を選ぶために始点ノード距離を計算する回数は最大でも N 回である。また,[キ]を選ぶ回数は,一度選ばれると当該ノードの最短距離は確定するので,最大でも N 回である。よって,最悪の場合の計算量は,[ク] である。
設問1
表 1 中の[ア]に入れる適切な字句を答えよ。
設問2
図 2 中の[イ]~[エ]に入れる適切な字句を答えよ。
設問3
〔最短経路の出力〕について答えよ。
(1) 本文中の下線①と[オ]について,挿入すべき代入文と[オ]に入れる行の番号を答えよ。行の番号については,最も小さい番号を答えること。ただし,図 2 中の現在の行の番号は図 3 及び図 4 の挿入によって変化しないものとする。
(2) 本文中の[カ]に入れる適切な字句を解答群の中から選び,記号で答えよ。
解答群
ア viaNode に格納してあるノード番号を
イ viaNode の要素番号を大きい方から
ウ viaNode の要素番号を小さい方から
設問4
〔計算量の考察〕について答えよ。
(1) 本文中の[キ]に入れる適切な字句を,本文中の字句を用いて 10 字以内で答えよ。
(2) 本文中の[ク]に入れる適切な字句を答えよ。
関連問題
本文が同じ・似ている問題を表示しています