ダイクストラ法

ダイクストラ法とは、グラフ上の最短経路問題をとくアルゴリズム。↓このページに詳しいアルゴリズムの説明がある。

 cf. ダイクストラ法(最短経路問題) – deq notes

Ruby でやってみた。
例題は、上のページにもあるこのグラフ(ただしノードにつけた番号のせいか上下が逆になっている)。

g

円(ノード)に番号がふられ、ノードをつなぐ辺(エッジ)にはそこを通るときのコスト(距離とも時間とも解釈できる)が付されている。この中の任意の 2 つのノードをつなぐ最短経路とコストを求めるのが最短経路問題だ。
今回は 0 番のノードをスタートし 5 番のノードをゴールとする最短経路とそのコストを求めてみる。

実行結果:

takatoh@nightschool $ ruby dijkstra.rb
10
0 -> 2 -> 4 -> 5

というわけで、最短経路は 0 -> 2 -> 4 -> 5、コストは 10 という答えが得られた。これは上のリンク先の答えと同じなので、あっていると思っていいだろう。

g1

ダイクストラ法” への1件のコメント

  1. ピンバック: ダイクストラ法(2) | blog.PanicBlanket.com

コメントを残す

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