最短経路問題の説明
図のような道路があります。①から⑥までの最短経路を求めます。いくつかの解法がありますが、ここでは代表的なダイクストラ法を簡便化した方法を用います。
終点から始点まで戻るように考えます。
地点ｉから直接に行ける地点ｊまでの距離を Ｃ(ｉ,ｊ) とします。
地点ｉから終点までの最短距離を Ｄ(ｉ) とします。
最短にするためには、地点ｉから地点Ｋに行けばよいとき、Ｐnext(ｉ) ＝Ｋとします。
ｉ＝６のとき、
⑥は終点なので、
Ｄ(６) ＝０
Ｐnext(ｉ) は定義する必要はない。
ｉ＝５のとき、
⑤から出ていく道は「⑤→⑥」だけです。そして、⑥は終点ですから、
Ｄ(５) ＝ Ｃ(５,６) ＝５
Ｐnext(５) ＝６
ｉ＝４のとき、
④から出ていく道は「④→⑥」と「④→⑤」の２本があります。
「④→⑥」のとき、Ａ ＝ Ｃ(４,６) ＝ ９
「④→⑤」のとき、Ｂ ＝ Ｃ(４,５)＋Ｄ(５) ＝ ６＋５＝１１
Ａ＜Ｂなので、
Ｄ(４) ＝ ５
Ｐnext(５) ＝６
このようにして、ｉ＝１まで行うと、次の表ができます。
ｉ Ｄ(ｉ) Ｐnext(ｉ)
６ ０ －
５ ５ ６
４ ９ ６
３ １９ ４
２ １３ ５
１ １７ ２
これから、最短距離は１７になります。
最短経路は、次の手順で求めます。始点①から始めます。
Ｐnext(１) ＝２ ②へ行く。
Ｐnext(２) ＝５ ⑤へ行く。
Ｐnext(５) ＝６ ⑥へ行く。
⑥が終点なので、最短経路は
１→２→５→６
定式化
地点の個数をＮとし、地点番号をｉ、終点の地点番号を Ｎlast（＝Ｎ）とします。
ｉ＝Ｎlast のとき、
Ｄ(Ｎlast) ＝０
ｉ＜Ｎlast のとき、
ｉを一つずつ減らして１になるまで行う。
Ｄ(ｉ) ＝ｍｉｎ｛ Ｄ(ｋ) ＋ Ｃ(ｉ,ｋ）｝
ｋ＝ｉ＋１，ｉ＋２，・・・，Ｎ で Ｃ(ｉ,ｋ）が存在するもの
Ｐnext(ｉ) ＝ ｍｉｎとなるｋの値
計算プログラム
カーナビゲーションでの応用
カーナビの主機能は、現在地から目的地への最短経路を求めることです。複雑な道路網などで膨大な地点数、経路数があるので、計算量を少なくすることが求められます。その代表的な手法に、上述のダイクストラ法をベースとした hub labeling法があります。その概要を示します。
- あらかじめ、地域別あるいは幹線別に、主要地点間の最短経路を計算した表をもっています。
- 主要地点Ａから主要地点Ｂの最短経路を求めるには、いくつかの中継地点を経由したＡからＢへの経路候補を探します（上の図が得られます）。主要地点間に絞っているので、規模は小さくなっています。
- その図を用いた計算により、主要地点Ａから主要地点Ｂの最短経路が得られます。
- 現在地と目的地が主要地点になっていればここまでの処理で完了ですが、そうでない場合は現在地とＡ、目的地とＢの間の最適経路を求め上の最適距離に加えますが、このときもどのＡ、Ｂを選ぶかで最適計算をすることになります。