趣味の数学とプログラム。楽しい数学の世界へようこそ!

最短経路問題 ダイクストラ法

目的地までの距離や時間、費用を最小におさえて行く経路を見つけるには、どうしたらいいでしょうか?

グラフ理論で、最短経路問題と呼ばれる問題です。
(グラフ理論でいうグラフは、点の集合と辺の集合で表されます。辺に重みがついているグラフを重みつきグラフと呼び、頂点間の移動距離、時間などを表すことができます)

最短経路を求めるアルゴリズムの一つが「ダイクストラ法」です。例を使いながら、解説していきましょう。ダイクストラ法では、辺の重みが0以上のグラフが対象となります。

 

グラフの辺に距離を記しました。Aからスタートするとします。

 

頂点の上の数字はスタート地点からの距離です。最短経路が確定した場合は、赤字にします。
Aはスタート地点なので、0で確定です。

①確定した頂点と隣接する頂点に、Aからの距離を記します(水色)
Bに1、Cに4、Dに5と記します。

②まだ確定していない頂点から、最短距離になるものを選び、経路を確定します
ここではBになるので、A→Bを確定。
以降、①と②の繰り返しです。
Bに隣接する頂点Cに、Aからの距離3を記します。3の方が小さいので、先に入っていた4(A→C)はキャンセルになります。

確定していない頂点のうち、最短距離になるのはCの3です。
B→Cを確定。Cに隣接する頂点E、Fに、それぞれAからの距離、Eに8,Fに9を記します。

確定していない頂点のうち、最短距離になるのはDの5です。
A→Dを確定。Dに隣接するEに、Aからの距離7を記します。先に入っていた8(C→E)はキャンセルになります。

確定していない頂点のうち、最短距離になるのはEの7です。
D→Eを確定。Eに隣接するG、Hに、それぞれAからの距離、Gに8,Hに10を記します。

確定していない頂点のうち、最短距離になるのはGの8です。
E→Gを確定。Gに隣接するHへのAからの距離は12ですが、先に入っていた10(E→H)の方が小さいので、そのままです。

確定していない頂点のうち、最短距離になるのはFの9です。
C→Fを確定。Fに隣接するHへのAからの距離は11ですが、先に入っていた10(E→H)の方が小さいので、そのままです。

最後にHです。E→Hを確定し、全ての頂点が確定したので処理を終えます。

ダイクストラ法

最短距離が確定した頂点と隣接する各頂点に、スタート地点からの距離を記入(先に数字が入っていれば、比較して小さい場合に置き換える)

②確定していない頂点のうち、距離が最短の頂点を確定

 
①②を全ての頂点が確定するまで繰り返します。

※ダイクストラ法では、スタート地点から各頂点への最短距離も確定します。
上の例で、Aから各頂点への最短距離は以下のようになります。

B 1
C 3(A→B→C)
D 5
E 7(A→D→E)
F 9(A→B→C→F)
G 8(A→D→E→G)
H 10(A→D→E→H)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です