Posted on 2016/06/14, 10:55 PM By admin22
ダイクストラ法という最短経路を求めるアルゴリズムをRubyのGraph Libraryを使ってテストしてみました。
環境: ruby 2.0.0p481 / MacOSX 10.10.5
インストール:
sudo gem install rgl
brew install graphviz
参考:
https://github.com/monora/rgl/issues/24
まずは参考サイトのデータをそのままテスト。
|
1 2 3 4 5 6 7 8 |
require 'rgl/base' require 'rgl/adjacency' require 'rgl/dijkstra' require 'rgl/dot' graph = RGL::AdjacencyGraph[2,53, 2,3, 3,8, 3,28, 3,39, 29,58, 8,35, 12,39, 10,29, 62,15, 15,32, 32,58, 58,44, 44,53] graph.write_to_graphic_file(fmt='jpg', dotfile='dijk') p graph.dijkstra_shortest_path(Hash.new(1), 39, 62) |
[39, 3, 2, 53, 44, 58, 32, 15, 62]
次に最短ルートを本当にとるか、ということで経路を増やしてみます。
|
1 2 3 4 5 6 7 8 9 |
require 'rgl/base' require 'rgl/adjacency' require 'rgl/dijkstra' require 'rgl/dot' graph = RGL::AdjacencyGraph[2,53, 2,3, 3,8, 3,28, 3,39, 29,58, 8,35, 12,39, 10,29, 62,15, 15,32, 32,58, 58,44, 44,53, 10,15, 8, 44, 58,15] graph.write_to_graphic_file(fmt='jpg', dotfile='dijk2') p graph.dijkstra_shortest_path(Hash.new(1), 39, 62) |
[39, 3, 8, 44, 58, 15, 62]
最後に、ルートにコストを加えて迂回させます。(2以上がコスト)
[39, 3, 2, 53, 44, 58, 32, 15, 62]
コストをかけた部分が避けられました。
|
1 2 3 4 5 6 7 8 9 10 |
require 'rgl/base' require 'rgl/adjacency' require 'rgl/dijkstra' require 'rgl/dot' graph = RGL::AdjacencyGraph[2,53, 2,3, 3,8, 3,28, 3,39, 29,58, 8,35, 12,39, 10,29, 62,15, 15,32, 32,58, 58,44, 44,53, 10,15, 8, 44, 58,15] cost = {[39,3]=>1, [3,8]=>2, [8,44]=>2, [3,2]=>1, [2,53]=>1, [53,44]=>1, [44,58]=>1, [58,15] => 3, [58,32]=>1, [32,15]=>1, [15,62]=>1, [39,12]=>1, [3,28]=>1, [8,35]=>1, [58,29]=>1, [29,10]=>1, [10,15]=>1} p graph.dijkstra_shortest_path(cost, 39, 62) |
まずは基本的な部分のテストでした。
Categories: 未分類 タグ: ruby