最短経路問題

最短経路問題とは? ── 出発地点から目的地までの最短経路を求める

例えば...

単純なアルゴリズム とても簡単, コンピュータを使わなくてもできる
でも,目的地までの経路の総数が非常に多い場合には???
効率的なアルゴリズムが必要
問題をモデル化しよう

説明を簡単にするために,最短経路問題をモデル化しましょう.

図の見方

目的:出発地点(地点1)から,目的地(地点6)までの最短経路(あるいは 最低料金経路)を求める

この図において,地点 1 から地点 6 へ行く場合,


地点数が800の場合の例を見てみよう

地点数が800で,距離は地点を結ぶ直線距離とした場合の 道路網で,下で説明しているダイクストラ法 というアルゴリズムで 最短経路を求めるデモがここにあります ので,ちょっと覗いてみてください.


ダイクストラ法 ── 最短経路問題に対するアルゴリズム

実は,最短経路問題は,問題としてはやさしい部類の問題で, 全経路を調べなくても効率的に最短経路が求められるアルゴリズム が知られています.ここでは,そのようなアルゴリズムの一つである ダイクストラ法について説明します. ダイクストラ法では,目的地への最短経路だけでなく, その他の全ての地点への最短経路を同時に求めることができます. 次の図で説明しましょう

以下で,順次,地点1からの最短距離が求まった地点は 灰色で塗り潰し,その上に地点1からの最短距離を赤色で 記入していくことにします. また,すでに最短距離が確定している地点に直接つながっている 地点をオレンジ色に塗り潰し, その上に青色で 「仮の最短距離」を書き込みます. この「仮の最短距離」は,それに至る直前の(最短距離が確定している) 地点にもとづいて更新します.

まず,出発地点1から地点1への距離はもちろん0で,確定していますから 次のようになります.

今最短距離が確定した地点1から直接行ける地点(2, 4, 5) に 仮の最短距離 をつけます. 今「仮の最短距離」は,今確定した地点(地点1)からの距離になります.

仮の最短距離が一番小さい地点を探します.それは,地点1から直接行ける 地点の中での最小値なので,その地点の仮の最短距離は,地点1からの 最短距離として確定します.今の場合,それは地点2となります. ここで,赤い線は,確定した最短経路 を表します.

あらたに確定した地点(地点2)から直接行ける地点の仮の最短距離を 更新します.地点5の仮の最短距離は 3 たっだのですが,地点2を経由すれば,

     地点2までの最短距離( = 1) + 2と5の間の距離 ( = 1)  = 2
で行けますので,地点5の仮の最短距離は 2 に更新します.また 地点 3 の仮の最短距離も 5 に更新されます.

以下,同じ操作を続けます.仮の最短距離が最小の地点は今度は地点4と 地点5の2個所あり,どちらを選んでも良いのですが,例えば地点4を選びます. すると,その仮の最短距離の2は確定です(もしも,地点4に至るもっと短い 経路があったのなら,その経路は,地点2か5を経由していることになりますが, 今,地点2は最小の仮の最短距離を持っていたわけですから,そういうことは あり得ません).

最小の仮の最短距離を持っている地点は地点5となり,

それにつながっている地点の仮の最短距離を更新します.

次に地点3が確定し,

最終的に,

となり,地点1からその他全ての地点への最短距離と最短経路が求まりました.

何だかとっても複雑そうですが,このダイクストラのアルゴリズムは, 原理は単純で非常に単純な手順で構成されていて簡単にコンピュータで 実行できます.

京都大学のグループによるダイクストラ法の デモンストレーションが,以下にありますので体験してみてください. 1ステップずつ実行したり,自動的に動かして様子を観察できたり します.

京都大学のアルゴリズム工学/アルゴリズムデータベース/ダイクストラ法のデモ
地点数800のデモ  最初のページに戻る