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

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

〔経路算定のモデル化〕

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

図1にノードが五つのグラフの例を示す。図1の例では，始点をV1のノードとし，終点をV5のノードとした場合の最短経路は，V1，V2，V3，V5のノードを順にたどる経路である。

クリックで拡大

図1　ノードが五つのグラフの例

〔始点から終点までの最短距離を求める手順〕

ダイクストラ法による始点から終点までの最短距離の算出は次のように行う。

最初に，各ノードについて，始点からそのノードまでの距離（以下，始点ノード距離という）を作業用に導入して十分に大きい定数としておく。ただし，始点の始点ノード距離は0とする。この時点では，どのノードの最短距離も確定していない。

次に，終点の最短距離が確定するまで，①〜③を繰り返す。ここで，始点との距離を算出する基準となるノードを更新起点ノードという。

〔図1の例における最短距離を求める手順と始点ノード距離〕

図1の例において，始点V1から終点V5までの経路に対して，上の①〜③を繰返し適用する。そのとき，更新起点ノードを選ぶたびに，更新起点ノードの始点ノード距離，更新起点ノードと隣接するノードの始点ノード距離，及び最短距離が確定していないノードの始点ノード距離を計算した内容を表1に示す。

注記1　INFは，定数で十分大きい数を表す。

注記2　<>内の数値は，当該ノードの始点ノード距離を表す。

〔最短距離の算出プログラム〕

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

〔最短経路の出力〕

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

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

〔計算量の考察〕

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